# Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs

arXiv: https://arxiv.org/abs/2506.08405 · HTML: https://mlsanity.com/paper/2506.08405/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 48 references that are in the map.
- First posted on arXiv 10 Jun 2025.

## Builds on (most cited first, 22 of 22)

- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [Query Complexity of Clustering with Side Information](https://mlsanity.com/paper/1706.07719/) (2017)
- [Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost](https://mlsanity.com/paper/1908.04976/) (2019)
- [Exact Recovery of Mangled Clusters with Same-Cluster Queries](https://mlsanity.com/paper/2006.04675/) (2020)
- [Same-Cluster Querying for Overlapping Clusters](https://mlsanity.com/paper/1910.12490/) (2019)
- [A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution](https://mlsanity.com/paper/1702.01208/) (2017)
- [On Learning Graphs with Edge-Detecting Queries](https://mlsanity.com/paper/1803.10639/) (2018)
- [Clustering with Queries under Semi-Random Noise](https://mlsanity.com/paper/2206.04583/) (2022)
- [Tight query complexity bounds for learning graph partitions](https://mlsanity.com/paper/2112.07897/) (2021)
- [Cut query algorithms with star contraction](https://mlsanity.com/paper/2201.05674/) (2022)
- [Graph Reconstruction via Distance Oracles](https://mlsanity.com/paper/1304.6588/) (2013)
- [Graph Connectivity and Single Element Recovery via Linear and OR Queries](https://mlsanity.com/paper/2007.06098/) (2020)
- [Optimal distance query reconstruction for graphs without long induced cycles](https://mlsanity.com/paper/2306.05979/) (2023)
- [Clustering with Non-adaptive Subset Queries](https://mlsanity.com/paper/2409.10908/) (2024)
- [Learning Partitions using Rank Queries](https://mlsanity.com/paper/2409.13092/) (2024)
- [Subpolynomial trace reconstruction for random strings and arbitrary deletion probability](https://mlsanity.com/paper/1801.04783/) (2018)
- [On the query complexity of connectivity with global queries](https://mlsanity.com/paper/2109.02115/) (2021)
- [Nearly Optimal Communication and Query Complexity of Bipartite Matching](https://mlsanity.com/paper/2208.02526/) (2022)
- [Graph Reconstruction via MIS Queries](https://mlsanity.com/paper/2401.05845/) (2024)
- [Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries](https://mlsanity.com/paper/2410.18704/) (2024)

## Abstract (arXiv)

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(fracm log nlog m) queries in expectation are both sufficient and necessary to adaptively reconstruct the graph. In contrast, we show that Omega(n2) non-adaptive queries are required, even when m = O(n). We also provide an O(mlog n + nlog2 n) query algorithm using only two rounds of adaptivity.