Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
Abstract
The graph reconstruction problem has been extensively studied under various query models. In this paper, we propose a new query model regarding the number of connected components, which is one of the most basic and fundamental graph parameters. Formally, we consider the problem of reconstructing an $n$-node $m$-edge graph with oracle queries of the following form: provided with a subset of vertices, the oracle returns the number of connected components in the induced subgraph. We show $\Theta(\frac{m \log n}{\log m})$ queries in expectation are both sufficient and necessary to adaptively reconstruct the graph. In contrast, we show that $\Omega(n^2)$ non-adaptive queries are required, even when $m = O(n)$. We also provide an $O(m\log n + n\log^2 n)$ query algorithm using only two rounds of adaptivity.
Cite
Text
Black et al. "Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs." Proceedings of Thirty Eighth Conference on Learning Theory, 2025.Markdown
[Black et al. "Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs." Proceedings of Thirty Eighth Conference on Learning Theory, 2025.](https://mlanthology.org/colt/2025/black2025colt-optimal/)BibTeX
@inproceedings{black2025colt-optimal,
title = {{Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs}},
author = {Black, Hadley and Mazumdar, Arya and Saha, Barna and Xu, Yinzhan},
booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory},
year = {2025},
pages = {315-343},
volume = {291},
url = {https://mlanthology.org/colt/2025/black2025colt-optimal/}
}