Lower bounds for graph reconstruction with maximal independent set queries

Abstract

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 $\hat{I}\text{c◯}(\hat{I}{”}^2\log (n/\hat{I}”)/\log \hat{I}”)$ queries to reconstruct $n$-vertex graphs of maximum degree $\hat{I}”$ with success probability at least $1/2$, and we further improve this lower bound to $\hat{I}\text{c◯}(\hat{I}{”}^2\log (n/\hat{I}”))$ for randomised non-adaptive algorithms. We also prove that deterministic non-adaptive algorithms require at least $\hat{I}\text{c◯}(\hat{I}{”}^3\log n/\log \hat{I}”)$ 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.

12 pages