Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

Graph Reconstruction with a Connected Components Oracle

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that graph reconstruction with a connected-components oracle is solvable in $O(\min\{m/\log m, \Delta^2, k^2\}\cdot \log n)$ queries and no faster than $\Omega(\min\{m, \Delta^2, k^2\})$, pinning the query complexity to…

desk verdict The CC oracle is a real contribution, the main bounds hold up, and the paper only needs a clarified Lemma 13 and a fixed Sep polarity before it is publishable. read the letter →

arxiv 2509.05002 v2 pith:E6MNKY4U submitted 2025-09-05 cs.DS

Juha Harviainen , Pekka Parviainen This is my paper · ORCID
classification cs.DS
keywords graphreconstructionquerycomplexityconnectedcomponentsoracletreewidthdegeneracymaximumdegreeadaptivealgorithmslowerbounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks how many queries a hidden graph needs if the only access is an oracle that, given any vertex subset, returns the exact list of connected components it induces. The answer it argues for is that the query count is governed by the graph's structural parameters and is essentially optimal. An adaptive randomized algorithm reconstructs any $n$-vertex graph with $m$ edges, maximum degree $\Delta$, and treewidth $k$ using $O(\min\{m/\log m, \Delta^2, k^2\}\cdot \log n)$ queries, and a separate algorithm handles graphs of degeneracy $d$ in $O(d^2\log^2 n)$ queries. Each upper bound is matched by a lower bound of $\Omega(m)$, $\Omega(\Delta^2)$, $\Omega(k^2)$, or $\Omega(d^2)$ queries, so the query complexity of this oracle is pinned down to within a logarithmic factor in $n$.

What carries the argument

The engine of the upper bounds is the witness event for a non-edge $uv$: a query set $Q$ that contains both $u$ and $v$ while excluding every neighbor of $u$ forces the oracle to report $u$ and $v$ in different components, and Lemma 1 bounds the probability of such a query under independent inclusion with probability $1/(p+1)$, giving the factor $1/p^2$ that becomes $O(p^2\log n)$ after repetition. For treewidth, the companion fact is that in a $k$-tree every non-edge is separated by some set of exactly $k$ vertices; sampling enough queries detects all such separators and yields a supergraph of treewidth at most $k$, which Algorithm 3 prunes by repeatedly extracting balanced separators of size at most $k+1$ and grouping queries by a $(k+1)$-coloring so that many components can be tested in parallel. The lower bound uses a family of two cliques of size $\eta$ joined by an arbitrary bipartite subgraph, on which every CC query has only two possible answers, so $\eta^2-1$ queries can distinguish only $2^{\eta^2-1}$ of the $2^{\eta^2}$ graphs.

What would settle it

The decisive check is the lower-bound family of Theorem 21: on two disjoint cliques of size $\eta$ with all $2^{\eta^2}$ possible bipartite edge sets, every CC query has exactly two possible outcomes, so an algorithm using $\eta^2-1$ queries has at most $2^{\eta^2-1}$ possible transcripts and must misidentify at least half of the graphs; any claimed algorithm with $o(\eta^2)$ queries must be run on this family and shown to exceed probability $1/2$, which would refute the lower bound.

Watch

Extended reading notes

Core claim

The central claim is that the connected-components oracle is quantitatively powerful: it returns enough information per query that the entire graph can be recovered with a number of queries that is polynomial in one of four structural parameters and only logarithmic in the number of vertices, and this is essentially optimal. Concretely, Theorem 17 gives an adaptive randomized algorithm using $O(\min\{m/\log m, \Delta^2, k^2\}\cdot \log n)$ CC queries for graphs with $m$ edges, maximum degree $\Delta$, and treewidth $k$, with success probability tending to 1; Theorem 20 adds an $O(d^2\log^2 n)$ bound for graphs of degeneracy $d$. Theorem 21 shows that no algorithm can succeed with probability above $1/2$ using $o(m)$, $o(\Delta^2)$, $o(k^2)$, or $o(d^2)$ queries, so the upper and lower bounds agree up to the $\log n$ factor. The paper also separates the CC oracle from the counting, maximal-independent-set, and separation oracles by proving polynomial query gaps in both simulation directions.

Load-bearing premise

The upper bounds depend on the connected-components oracle answering every query with the exact, complete list of components, and on the randomized first phase failing on no non-edge, so that it really returns an outer graph of controlled treewidth; slip on either and the separator-based pruning can keep false edges.

Editorial extensions

If this is right

  • For any graph with bounded treewidth $k$, reconstruction needs only $O(k^2\log n)$ CC queries and two rounds of adaptivity, so a single additional adaptive round drops the worst-case query count from $\Omega(n^2)$ to polylogarithmic in $n$.
  • For graphs with bounded degeneracy $d$—including planar graphs, where $d\le 5$—reconstruction uses $O(d^2\log^2 n)$ queries, which stays polylogarithmic even when maximum degree and treewidth are unbounded.
  • No algorithm can do better than $\Omega(m)$, $\Omega(\Delta^2)$, $\Omega(k^2)$, or $\Omega(d^2)$ CC queries with probability above $1/2$, so all three upper bounds are within a $\log n$ factor of optimal.
  • The CC oracle cannot be replaced by the counting oracle, the maximal-independent-set oracle, or the separation oracle without a polynomial blowup in the number of queries on some instances, and neither direction of simulation between CC and MIS oracles is efficient.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the logarithmic gap is ever closed, the likely route is a sharper counting argument for Lemma 1 that depends on the number of edges rather than on $n$; the lower-bound family already rules out transcript counts below $\eta^2$, so the open target is the single $\log n$ factor.
  • The two-round adaptivity phenomenon suggests a general principle for high-information oracles: one round of adaptivity can collapse an $\Omega(n^2)$ non-adaptive barrier to polylogarithmic query complexity, and testing whether weaker oracles such as returning one representative vertex per component retain this effect would map the information-theoretic boundary.
  • The two-clique lower-bound construction is transferable: any oracle whose answers on that family have only two possible outcomes will inherit the $\Omega(\eta^2)$ barrier, so the same counting argument likely applies to other set-query oracles with bounded transcript branching.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper introduces the connected components (CC) oracle for graph reconstruction, in which a query returns the full partition of the induced subgraph into connected components. The main results are: a randomized adaptive algorithm using O(min{m/log m, Δ^2, k^2} log n) CC queries for graphs with m edges, maximum degree Δ, and treewidth k; an O(d^2 log^2 n) algorithm for degeneracy d; and a lower bound of Ω(min{m, Δ^2, k^2}) for randomized adaptive algorithms, with a non-adaptive lower bound of Ω(n^2) even for treewidth 2. The paper also compares the CC oracle with the connected-component-counting, maximal-independent-set, and separation oracles. The upper bounds are built from a sampling scheme for bounded-degree graphs, a treewidth-supergraph construction followed by separator-based pruning, and a peeling algorithm for bounded-degeneracy graphs.

Significance. If the proofs are completed, the paper gives a nearly tight characterization of the CC oracle: the upper and lower bounds differ by at most a logarithmic factor in n for m, Δ, and k, and by a polylogarithmic factor for d. The sampling and lower-bound arguments (Theorems 3, 11, 12, and 21) are sound, and the comparisons with other oracles are interesting. The main unresolved point is the proof of Lemma 13, which is central to the treewidth bound but is currently too terse to verify; the reversed Yes/No mapping in Theorem 28 is a localized but real correctness error. With those fixed, the contribution would be a solid addition to the query-complexity literature.

major comments (2)
  1. [3.3, Lemma 13] The proof does not specify the families K1 and K2 precisely enough to be checked, and the argument that the queries separate every non-edge is incomplete. The sentence 'The vertices in outside S′ included in the set Q are of the same color. Thus, they do not have neighbors that is not in S′ is included in the set Q' is not a valid proof step: same-color vertices are independent, but this does not by itself exclude a neighbor of v from Q, nor does it show that an included neighbor cannot create a path from u to v. The construction 'every vertex in S′ appears at least once in a set with each color' guarantees individual inclusion only; for pairs (u,v) with u,v∈S′ in different separators the simultaneous-inclusion condition is not established. Since different separators lie in different connected components of G+[R], those pairs may be irrelevant, but the paper should say so explicitly. The K1 condition 'at most two elements from X′' also needs a precise construction tying it to the h(h−1)/2 count. Because Lemma 13 underpins Theorems 14, 16, and 17, the central O(k^2 log n) upper bound is load-bearing on this repair.
  2. [5.3, Theorem 28] The semantics of the Sep oracle are reversed in the proof. Sep(v,w,V\S) returns Yes exactly when v and w are in different connected components of G[V\(V\S)] = G[S]. The upper-bound procedure in the proof says 'If the answer is Yes, then v and w are in the same connected component. Otherwise, they are in different connected components,' which is exactly backwards; the proposed procedure would output the complement of the connected components. The theorem statement is therefore false as written. The lower-bound paragraph appears repairable under the correct semantics, but the proof must be rewritten.
minor comments (5)
  1. [Algorithm 3, lines 6–21] The pseudocode places the query-execution loop after the while loop, while the proof of Lemma 13 says queries are conducted after each iteration. The algorithm should state explicitly that all accumulated queries are executed only after R is empty, or the loop should be moved inside the while loop, and the proof should match the pseudocode.
  2. [3.3.2, Theorem 16] The doubling test requires checking whether the output of Algorithm 2 has treewidth larger than D, but the paper does not state how this test is performed or what computational resources it uses. If the paper's complexity measure is query count only, this should be stated explicitly.
  3. [5.1, Theorem 23] The statement 'No algorithm can solve all instances ... with Ω(np/logn) #CC queries' should read 'requires Ω(np/log n) #CC queries' or equivalently 'cannot solve with o(np/log n) queries'.
  4. [Table 1] The entry for Corollary 2 uses the notation 'mlog(n)/log(m)', which should be 'm log(n)/log(m)'.
  5. [3.2.2, paragraph on λ] The claim 'Clearly, λ is bounded by the maximum degree, since each of the disjoint paths has to use one of the edges adjacent to the starting vertex of the path' is slightly imprecise because the direct edge uv itself uses an edge adjacent to u; the bound should be λ ≤ Δ−1 for non-adjacent pairs, or the sentence should be rephrased.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the upper and lower bounds are derived from oracle-simulation arguments, random-sampling witnesses, and adversarial lower-bound families, not by defining the target in terms of itself.

full rationale

The derivation chain is self-contained. Corollary 2 is obtained by simulating the #CC oracle of Black et al. with the stronger CC oracle; that is a reduction from a weaker oracle, not a use of the target result. The bounded-degree algorithms (Theorems 3, 10, 11) and the supergraph construction (Lemma 12) use random subset sampling and p-query-schemes whose witness condition is stated directly in terms of the CC answers; the claimed detection event is exactly that a non-edge appears in distinct connected components, which is what the oracle returns. No parameter is fitted to a subset of answers and then announced as a prediction. The treewidth pruning step (Lemma 13) assumes only that G+ is a treewidth-k supergraph and builds query families K1 and K2 from that supergraph; it does not assume the hidden graph's edges. The lower bound (Theorem 21) constructs a family for which every CC query has only two possible outputs and applies Yao's lemma; it does not import the upper bound. The non-adaptive lower bound is proved separately in Corollary 22 rather than inherited by simulation from the weaker #CC oracle, so it is not a renaming of a known result. The only self-citation is [19], used in Section 5.3 and the Conclusions to introduce the pairwise-connectivity parameter lambda and a separation-oracle lower bound; this is neither load-bearing for the min{m/log m, Delta^2, k^2} bound nor a uniqueness theorem invoked to rule out alternatives. The admitted absence of efficient explicit p-query-scheme constructions (Section 3.2.1) and the terse K1/K2 proof of Lemma 13 are correctness or rigor concerns, but an under-specified construction is not a circular reduction: the query bounds are not defined in terms of the hidden graph and are not obtained by renaming oracle outputs. Hence score 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper is purely analytical. It introduces a new query model (the CC oracle) but no new physical or metaphysical entities. All parameters (m, Δ, k, d) are graph parameters given as inputs, not fitted values. The axioms listed are standard mathematical facts used as building blocks; none are ad hoc to this paper.

assumptions (5)
  • standard math Fact 1: In a k-tree, every non-edge uv is separated by some set S of size k such that u and v lie in different components of G[V\S].
    Used in Algorithm 2 (Lemma 12) to argue that k random exclusions isolate non-edges of a k-tree supergraph.
  • standard math Fact 2: Every graph of treewidth k has a 1/2-balanced separator of order at most k+1.
    Used in Algorithm 3 to recursively split components into smaller pieces.
  • standard math Fact 3: Every graph of treewidth at most k can be colored with k+1 colors.
    Used in Algorithm 3 so that a query set containing all vertices of one color outside the separators is an independent set, which is essential for detecting non-edges.
  • standard math Yao's lemma: existence of a good randomized algorithm implies existence of a good deterministic algorithm against a fixed distribution.
    Used in Theorem 21 and Theorem 23 to convert randomized lower bounds into deterministic ones.
  • standard math Every graph of treewidth k is a subgraph of some k-tree.
    Used in Lemma 12 to choose a fixed k-tree supergraph whose non-edges the algorithm attempts to detect.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Graph Reconstruction with a Connected Components Oracle." pith.science (2026). https://pith.science/paper/E6MNKY4U

@misc{pith2026250905002,
  author       = {Pith},
  title        = {Pith review of: Graph Reconstruction with a Connected Components Oracle},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/E6MNKY4U}},
  note         = {Machine review of arXiv:2509.05002}
}
abstract

In the Graph Reconstruction (GR) problem, the goal is to recover a hidden graph by utilizing some oracle that provides limited access to the structure of the graph. The interest is in characterizing how strong different oracles are when the complexity of an algorithm is measured in the number of performed queries. We study a novel oracle that returns the set of connected components (CC) on the subgraph induced by the queried subset of vertices. Our main contributions are as follows: 1. For a hidden graph with $n$ vertices, $m$ edges, maximum degree $\Delta$, and treewidth $k$, GR can be solved in $O(\min\{m / \log m, \Delta^2, k^2\} \cdot \log n)$ CC queries by an adaptive randomized algorithm. 2. For a hidden graph with $n$ vertices and degeneracy $d$, GR can be solved in $O(d^2 \log^2 n)$ CC queries by an adaptive randomized algorithm. 3. For a hidden graph with $n$ vertices, $m$ edges, maximum degree $\Delta$, and treewidth $k$, no algorithm can solve GR in $o(\min\{m, \Delta^2, k^2\})$ CC queries.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Experimental Assortments for Choice Estimation and Nest Identification

    stat.ME 2026-02 conditional novelty 7.0 of 10

    A binary-code experiment design with O(log n) assortments, plus a boost-factor algorithm, provably recovers substitution nests in Nested Logit models and improves choice prediction.

Reference graph

Works this paper leans on

29 extracted references · 22 canonical work pages · cited by 1 Pith paper

  1. [19]

    Fomin, and Pekka Parviainen

    Tuukka Korhonen, Fedor V. Fomin, and Pekka Parviainen. Structural perspective on constraint-based learning of M arkov networks. In International Conference on Artificial Intelligence and Statistics, AISTATS 2024 , volume 238 of Proceedings of Machine Learning Research , pages 1855--1863. PMLR , 2024

    work page 2024

  2. [1]

    Hasan Abasi and Nader H. Bshouty. On learning graphs with edge-detecting queries. In Algorithmic Learning Theory, ALT 2019 , volume 98 of Proceedings of Machine Learning Research , pages 3--30. PMLR , 2019

    2019

  3. [2]

    Graph reconstruction with a betweenness oracle

    Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, and Morten St \" o ckel. Graph reconstruction with a betweenness oracle. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 , volume 47 of LIPIcs , pages 5:1--5:14. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2016

    work page 2016

  4. [3]

    Learning a hidden subgraph

    Noga Alon and Vera Asodi. Learning a hidden subgraph. SIAM J. Discret. Math. , 18(4):697--712, 2005

    2005

  5. [4]

    Learning a hidden matching

    Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov. Learning a hidden matching. SIAM J. Comput. , 33(2):487--501, 2004

    2004

  6. [5]

    Color-coding

    Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM , 42(4):844--856, 1995

    work page 1995

  7. [6]

    Learning a hidden graph using O ( n) queries per edge

    Dana Angluin and Jiang Chen. Learning a hidden graph using O ( n) queries per edge. J. Comput. Syst. Sci. , 74(4):546--556, 2008

    work page 2008

  8. [7]

    Shankar Ram

    Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Mat \' u s Mihal \' a k, and L. Shankar Ram. Network discovery and verification. IEEE J. Sel. Areas Commun. , 24(12):2168--2181, 2006

    2006

Show all 29 references
  1. [8]

    An optimal procedure for gap closing in whole genome shotgun sequencing

    Richard Beigel, Noga Alon, Simon Kasif, Mehmet Serkan Apaydin, and Lance Fortnow. An optimal procedure for gap closing in whole genome shotgun sequencing. In Proceedings of the Fifth Annual International Conference on Computational Biology, RECOMB 2001 , pages 22--30. ACM , 2001

    2001

  2. [9]

    Optimal graph reconstruction by counting connected components in induced subgraphs

    Hadley Black, Arya Mazumdar, Barna Saha, and Yinzhan Xu. Optimal graph reconstruction by counting connected components in induced subgraphs. In The Thirty Eighth Annual Conference on Learning Theory, COLT 2025 , volume 291 of Proceedings of Machine Learning Research , pages 31...

    2025

  3. [10]

    Combinatorial search on graphs motivated by bioinformatics applications: A brief survey

    Mathilde Bouvel, Vladimir Grebinski, and Gregory Kucherov. Combinatorial search on graphs motivated by bioinformatics applications: A brief survey. In Proceedings of the 31st International Workshop Graph-Theoretic Concepts in Computer Science, WG 2005 , volume 3787 of Lecture ...

    2005

  4. [11]

    C. K. Chow and C. N. Liu. Approximating discrete probability distributions with dependence trees. IEEE Trans. Inf. Theory , 14(3):462--467, 1968

    1968

  5. [12]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms . Springer, 2015

    2015

  6. [13]

    Reconstructing a hamiltonian cycle by querying the graph: Application to DNA physical mapping

    Vladimir Grebinski and Gregory Kucherov. Reconstructing a hamiltonian cycle by querying the graph: Application to DNA physical mapping. Discret. Appl. Math. , 88(1-3):147--165, 1998

    1998

  7. [14]

    Optimal reconstruction of graphs under the additive model

    Vladimir Grebinski and Gregory Kucherov. Optimal reconstruction of graphs under the additive model. Algorithmica , 28(1):104--124, 2000

    2000

  8. [15]

    Graph reconstruction and verification

    Sampath Kannan, Claire Mathieu, and Hang Zhou. Graph reconstruction and verification. ACM Trans. Algorithms , 14(4):40:1--40:30, 2018

    2018

  9. [16]

    Karger and Nathan Srebro

    David R. Karger and Nathan Srebro. Learning M arkov networks: maximum bounded tree-width graphs. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, SODA 2001 , pages 392--401. ACM/SIAM , 2001

    2001

  10. [17]

    Probabilistic Graphical Models - Principles and Techniques

    Daphne Koller and Nir Friedman. Probabilistic Graphical Models - Principles and Techniques . MIT Press, 2009

    2009

  11. [18]

    Graph reconstruction via MIS queries

    Christian Konrad, Conor O'Sullivan, and Victor Traistaru. Graph reconstruction via MIS queries. In Proceedings of the 16th Conference on Innovations in Theoretical Computer Science, ITCS 2025 , volume 325 of LIPIcs , pages 66:1--66:19. Schloss Dagstuhl - Leibniz-Zentrum f \" u...

    2025

  12. [20]

    Lick and Arthur T

    Don R. Lick and Arthur T. White. k-degenerate graphs. Canadian Journal of Mathematics , 22(5):1082–1096, 1970

    1970

  13. [21]

    A simple algorithm for graph reconstruction

    Claire Mathieu and Hang Zhou. A simple algorithm for graph reconstruction. Random Struct. Algorithms , 63(2):512--532, 2023

    2023

  14. [22]

    Lukas Michel and Alex D. Scott. Lower bounds for graph reconstruction with maximal independent set queries. Theor. Comput. Sci. , 1034:115121, 2025

    2025

  15. [23]

    Explicit nonadaptive combinatorial group testing schemes

    Ely Porat and Amir Rothschild. Explicit nonadaptive combinatorial group testing schemes. IEEE Transactions on Information Theory , 57(12):7982--7989, 2011

    2011

  16. [24]

    Learning and verifying graphs using queries with a focus on edge counting

    Lev Reyzin and Nikhil Srivastava. Learning and verifying graphs using queries with a focus on edge counting. In Proceedings of the Eighteenth International Conference on Algorithmic Learning Theory, ALT 2007 , volume 4754 of Lecture Notes in Computer Science , pages 285--297. ...

    2007

  17. [25]

    Reconstruction and verification of chordal graphs with a distance oracle

    Guozhen Rong, Wenjun Li, Yongjie Yang, and Jianxin Wang. Reconstruction and verification of chordal graphs with a distance oracle. Theor. Comput. Sci. , 859:48--56, 2021

    2021

  18. [26]

    A divide-and-conquer approach for reconstruction of \ C_ 5 \ -free graphs via betweenness queries

    Guozhen Rong, Yongjie Yang, Wenjun Li, and Jianxin Wang. A divide-and-conquer approach for reconstruction of \ C_ 5 \ -free graphs via betweenness queries. Theor. Comput. Sci. , 917:1--11, 2022

    2022

  19. [27]

    Donald J. Rose. On simple characterizations of k-trees. Discret. Math. , 7(3-4):317--322, 1974

    1974

  20. [28]

    Sandeep Sen and V. N. Muralidhara. The covert set-cover problem with application to network discovery. In Proceedings of the 4th International Workshop on Algorithms and Computation, WALCOM 2010 , volume 5942 of Lecture Notes in Computer Science , pages 228--239. Springer, 2010

    2010

  21. [29]

    The chromatic number of oriented graphs

    \' E ric Sopena. The chromatic number of oriented graphs. J. Graph Theory , 25(3):191--205, 1997

    1997

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.