mlsanityData to 14 Oct 2026

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs

arXiv 2506.08405 ↗First posted 10 Jun 2025cs.DS cs.IT cs.LGcited by 0

Not on the map. Why?

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.

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

22 of 48 references.

References · 22

  1. 2014Dimensionality Reduction for k-Means Clustering and Low Rank Approximationcited by 48
  2. 2017Clustering with Noisy Queriescited by 34
  3. 2016Clustering with Same-Cluster Queriescited by 29
  4. 2017Query Complexity of Clustering with Side Informationcited by 20
  5. 2019Correlation Clustering with Same-Cluster Queries Bounded by Optimal Costcited by 16
  6. 2020Exact Recovery of Mangled Clusters with Same-Cluster Queriescited by 13
  7. 2019Same-Cluster Querying for Overlapping Clusterscited by 11
  8. 2017A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolutioncited by 9
  9. 2018On Learning Graphs with Edge-Detecting Queriescited by 9
  10. 2022Clustering with Queries under Semi-Random Noisecited by 8
  11. 2021Tight query complexity bounds for learning graph partitionscited by 5
  12. 2022Cut query algorithms with star contractioncited by 4
10 more
  1. 2013Graph Reconstruction via Distance Oraclescited by 3
  2. 2020Graph Connectivity and Single Element Recovery via Linear and OR Queriescited by 3
  3. 2023Optimal distance query reconstruction for graphs without long induced cyclescited by 3
  4. 2024Clustering with Non-adaptive Subset Queriescited by 3
  5. 2024Learning Partitions using Rank Queriescited by 3
  6. 2018Subpolynomial trace reconstruction for random strings and arbitrary deletion probabilitycited by 2
  7. 2021On the query complexity of connectivity with global queriescited by 2
  8. 2022Nearly Optimal Communication and Query Complexity of Bipartite Matchingcited by 1
  9. 2024Graph Reconstruction via MIS Queriescited by 1
  10. 2024Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queriescited by 1

Built on by

Not cited yet.