Lower bounds for graph reconstruction with maximal independent set queries
<|reference_start|>Lower bounds for graph reconstruction with maximal independent set queries: 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 $\Omega(\Delta^2 \log(n / \Delta) / \log \Delta)$ queries to reconstruct $n$-vertex graphs of maximum degree $\Delta$ with success probability at least $1/2$, and we further improve this lower bound to $\Omega(\Delta^2 \log(n / \Delta))$ for randomised non-adaptive algorithms. We also prove that deterministic non-adaptive algorithms require at least $\Omega(\Delta^3 \log n / \log \Delta)$ 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.<|reference_end|>
@article{michel2024lower,
    title={Lower bounds for graph reconstruction with maximal independent set
  queries},
    author={Lukas Michel, Alex Scott},
    journal={arXiv preprint arXiv:2404.03472},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.03472},
    primaryClass={cs.DS math.CO}
}