# Tight query complexity bounds for learning graph partitions

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 26 references that are in the map.
- First posted on arXiv 15 Dec 2021.

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

- [Graph Reconstruction via Distance Oracles](https://mlsanity.com/paper/1304.6588/) (2013)
- [A Simple Algorithm for Graph Reconstruction](https://mlsanity.com/paper/2112.04549/) (2021)

## Built on by (most cited first, 5 of 5)

- [Learning Partitions with Optimal Query and Round Complexities](https://mlsanity.com/paper/2505.05009/) (2025)
- [Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle](https://mlsanity.com/paper/2305.13402/) (2023)
- [Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs](https://mlsanity.com/paper/2506.08405/) (2025)
- [Exact Learning of Weighted Graphs Using Composite Queries](https://mlsanity.com/paper/2511.14882/) (2025)
- [Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds](https://mlsanity.com/paper/2608.02176/) (2026)

## Abstract (arXiv)

Given a partition of a graph into connected components, the membership oracle asserts whether any two vertices of the graph lie in the same component or not. We prove that for n≥ k≥ 2, learning the components of an n-vertex hidden graph with k components requires at least (k-1)n-binom k2 membership queries. Our result improves on the best known information-theoretic bound of Omega(nlog k) queries, and exactly matches the query complexity of the algorithm introduced by [Reyzin and Srivastava, 2007] for this problem. Additionally, we introduce an oracle, with access to which one can learn the number of components of G in asymptotically fewer queries than learning the full partition, thus answering another question posed by the same authors. Lastly, we introduce a more applicable version of this oracle, and prove asymptotically tight bounds of widetildeTheta(m) queries for both learning and verifying an m-edge hidden graph G using it.