2024/04/04 by Michel, Lukas, Scott, Alex · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2404.03472
We investigate the number of maximal independent set queries required to reconstruct the edges of a hidden graph. We show that randomised adaptive algorithms need at least Ω(Δ2 log(n / Δ) / log Δ) queries to reconstruct n-vertex graphs of maximum degree Δ with success probability at least 1/2, and we further improve this lower bound to Ω(Δ2 log(n / Δ)) for randomised non-adaptive algorithms. We also prove that deterministic non-adaptive algorithms require at least Ω(Δ3 log n / log Δ) queries. This improves bounds of Konrad, O'Sullivan, and Traistaru, and answers one of their questions. The proof of the lower bound for deterministic non-adaptive algorithms relies on a connection to cover-free families, for which we also improve known bounds.