Lower bounds for graph reconstruction with maximal independent set queries

Journal article

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 Ω(Δ2log⁡(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 Ω(Δ2log⁡(n/Δ)) for randomised non-adaptive algorithms. We also prove that deterministic non-adaptive algorithms require at least Ω(Δ3log⁡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.

Authors: Michel, L; Scott, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Theoretical Computer Science
• Volume: 1034
• Article number: 115121
• Publication date: 2025-02-11
• Acceptance date: 2025-02-10
• DOI: 10.1016/j.tcs.2025.115121
• EISSN: 1879-2294
• ISSN: 0304-3975
• Language: English
• Keywords: cover-free families; graph reconstruction; maximal independent set queries