Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
This addresses a fundamental problem in graph theory and algorithms, providing optimal query bounds for a new model, though it is incremental in the context of existing reconstruction literature.
The paper tackles the graph reconstruction problem using a new query model based on counting connected components in induced subgraphs, showing that Θ(m log n / log m) queries are optimal for adaptive reconstruction, while non-adaptive methods require Ω(n²) queries.
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 $Θ(\frac{m \log n}{\log m})$ queries in expectation are both sufficient and necessary to adaptively reconstruct the graph. In contrast, we show that $Ω(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.