Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs

摘要

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 Θ(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(mlog n + nlog^2 n) query algorithm using only two rounds of adaptivity.