Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs

Hadley Black, Arya Mazumdar, Barna Saha, Yinzhan Xu
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:315-343, 2025.

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 this Paper

BibTeX
@InProceedings{pmlr-v291-black25a, 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}, pages = {315--343}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/black25a/black25a.pdf}, url = {https://proceedings.mlr.press/v291/black25a.html}, 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.} }
Endnote
%0 Conference Paper %T Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs %A Hadley Black %A Arya Mazumdar %A Barna Saha %A Yinzhan Xu %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-black25a %I PMLR %P 315--343 %U https://proceedings.mlr.press/v291/black25a.html %V 291 %X 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.
APA
Black, H., Mazumdar, A., Saha, B. & Xu, Y.. (2025). Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:315-343 Available from https://proceedings.mlr.press/v291/black25a.html.

Related Material