{"id":"83679a79-72a8-4b81-a529-b2e59c75bfe1","arxiv_id":"2509.05002","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A hidden graph on n vertices can be reconstructed from O(min{m/log m, Δ^2, k^2}·log n) connected-component queries, and no algorithm can do better than Ω(min{m, Δ^2, k^2}) queries.","lead":"The paper studies a new oracle that, given any subset of vertices, returns the exact connected components of the hidden graph on that subset, and asks how many such queries are needed to reconstruct the whole graph. It proves near-tight upper and lower bounds in terms of edges, maximum degree, treewidth, and degeneracy, and compares the oracle to previously studied oracles.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Treewidth upper bound rests on Lemma 13, whose K1/K2 query families are not explicitly constructed and whose separation argument is incomplete; if the intended construction fails, the O(k^2 log n) claim collapses.","rationale":"In good faith, the paper's main structure is sound: the bounded-degree and degeneracy algorithms are standard concentration arguments, the lower bound family in Theorem 21 gives a genuine Omega(min(m, Delta^2, k^2)) information-theoretic barrier, and the combination in Theorem 17 is valid if the component algorithms are valid. The most load-bearing soft spot is the treewidth branch, specifically Lemma 13. The reader already flagged Lemma 13 as terse and under-specified; my read agrees that this is the place where the central claim is least secure. The lower-bound family works, and the side-result polarity error in Theorem 28 is real but does not affect the main theorem. The concern I raise is not an accusation of a false result; it is a concrete proof gap. The paper asserts the existence of K1 and K2 with separation properties, but the proof never defines them precisely, and the stated sufficient condition is not actually satisfied by the described K2 sets. This is addressable in revision by supplying an explicit construction and a corrected separation argument, which is why the verdict should remain CONDITIONAL rather than being upgraded or rejected.","tokens_in":17034,"tokens_out":38014,"duration_ms":364207,"concrete_test":"Formalize an explicit construction: for K1, take all edges of each separator's clique colored with h colors (matching per color); for K2, for each color use h rounds, in each round choosing one vertex from every separator so that each vertex of S' appears in exactly one round of its color. Then exhaustively verify Lemma 13 for all hidden graphs G on n <= 7 vertices and all supergraphs G+ with treewidth <= 2: for every vertex v in a separator X', every u of the same color class (K2) or same separator (K1), and every resulting query Q, check that if uv is not in E(G) then u and v are in different components of G[Q]. If a counterexample appears, Lemma 13 is false as stated; if none appears, the construction should be written into the proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central O(k^2 log n) treewidth algorithm (Theorems 14, 16, and hence the min-theorem 17) depends on Lemma 13, which asserts that Algorithm 3 prunes a treewidth-k supergraph to the hidden graph using only O(k^2 log n) CC queries. The proof does not actually construct the query families K1 and K2; it only states rough conditions ('at most two elements from each X''; 'one element from each X'' and all vertices of one color') and then claims a separation property. The stated sufficient condition for detecting a non-edge uv, that Q contains u,v and no other neighbor of v, is not met by the described K2 sets: a K2 set of v's color class includes every vertex of that color outside S', and such vertices can be neighbors of v (when the color differs from v's). The intended argument must instead use that same-color vertices are independent and that the set contains only v from v's separator; this requires a specific assignment of separator representatives that is left unspecified. If K1/K2 cannot be instantiated with the needed property, Algorithm 3 may fail to delete a non-edge, and the core treewidth upper bound would be unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17198,"tokens_out":18171,"duration_ms":164524,"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":[{"comment":"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.","section":"3.3, Lemma 13"},{"comment":"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.","section":"5.3, Theorem 28"}],"minor_comments":[{"comment":"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.","section":"Algorithm 3, lines 6–21"},{"comment":"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.","section":"3.3.2, Theorem 16"},{"comment":"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'.","section":"5.1, Theorem 23"},{"comment":"The entry for Corollary 2 uses the notation 'mlog(n)/log(m)', which should be 'm log(n)/log(m)'.","section":"Table 1"},{"comment":"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.","section":"3.2.2, paragraph on λ"}],"recommendation":"major_revision","confidential_remarks":"I see no reason to doubt the main sampling and lower-bound arguments. The two issues above are localized; if the authors provide a full proof of Lemma 13 and correct Theorem 28, I would be willing to accept the revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a good paper. The connected-components oracle is new, and the main result — O(min{m/log m, Δ², k²} log n) adaptive queries with a matching Ω(min{m, Δ², k²}) lower bound — is real. The treewidth and degeneracy algorithms are new; the bounded-degree part is an honest adaptation of Konrad et al.'s MIS-query technique, and the authors say so. The lower-bound family is simple and works. I would send this to a serious referee.\n\nBest part: the lower/upper pairing. They pin down query complexity up to a log factor for m, Δ, k, and d, and the oracle separations clarify what CC queries buy you over #CC, MIS, and Sep. Theorem 24 (star needs Ω(n) MIS queries but O(log n) CC queries) is a clean illustration.\n\nSoft spots, in order of real weight. First, Lemma 13 is under-specified. The K1 and K2 families are never explicitly constructed; the proof asserts a separation property that, as written, is not met by the described K2 sets. The stress-test worry lands as a wording problem, not a fatal one: with the natural slot-based construction, the target vertex u is isolated in the query graph unless uv is an edge, because same-color vertices are independent and vertices from other components have no edges to v's component. The proof should say that, and the 'no other neighbors of v' sentence is wrong as written. This needs a rewrite, not a new idea.\n\nSecond, Theorem 28 has a genuine polarity error: Sep returns Yes for different components, but the upper-bound proof treats Yes as same component. Flip the comparison and the procedure works; the lower bound is fine. It is a side result, so the main contributions are untouched.\n\nThird, the union-bound notation in Theorem 3 is sloppy (X_i is an event, not a variable; indexing over 'edges' should be non-edges). Minor.\n\nThe central proofs — random sampling, balanced-separator pruning, Yao lower bound — are correct in main lines. Citation pattern is fair; the MIS lineage is credited and the self-citation to [19] is legitimate context. For peer review, I would ask for the K1/K2 construction and the Sep flip, then accept. A desk reject would be wrong.","headline":"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.","tokens_in":17775,"tokens_out":13866,"would_cite":true,"duration_ms":123034,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["graph reconstruction","query complexity","connected components oracle","treewidth","degeneracy","maximum degree","adaptive algorithms","lower bounds"],"falsifier":"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.","tokens_in":16772,"feed_emoji":"🔍","tokens_out":12436,"duration_ms":98780,"temperature":0.7,"pith_summary":"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$.","feed_headline":"Connected-components oracle rebuilds graphs in near-optimal queries","feed_subtitle":"Upper and lower bounds agree to within O(log n) for m, Δ, treewidth k, and degeneracy d.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the edge-counting upper bound that the CC oracle simulates directly, and the non-adaptive $\\Omega(n^2)$ lower bound for the counting oracle that is transferred to CC queries.","marker":"[9]"},{"why":"Provides the randomized query strategy of sampling vertex subsets with controlled inclusion probabilities, plus the witness and query-scheme derandomization used by the bounded-degree algorithms.","marker":"[18]"},{"why":"Gives the fact that every non-edge of a $k$-tree is separated by a set of exactly $k$ vertices, which drives the bounded-treewidth supergraph construction.","marker":"[27]"},{"why":"Supplies the balanced-separator theorem for bounded-treewidth graphs that the pruning algorithm needs at each recursive step.","marker":"[12]"},{"why":"Supplies the $(k+1)$-coloring fact for bounded-treewidth graphs used to parallelize separator queries by color.","marker":"[29]"},{"why":"Provides the splitter construction that turns randomized query schemes into explicit polynomial-time p-Query-Schemes for derandomization.","marker":"[5]"},{"why":"Establishes the lower bound on separation queries in terms of maximum pairwise connectivity, which the paper extends to the CC oracle and complements with an $O(\\lambda^2\\log n)$ bound.","marker":"[19]"}],"fun_headline_variants":["CC oracle reconstructs graphs in near-optimal queries","Connected-components oracle: near-optimal graph recovery","Graph recovery via components oracle is near-optimal","Components oracle matches lower bound up to log factor"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["CC oracle reconstructs graphs in near-optimal queries","Connected-components oracle: near-optimal graph recovery","Graph recovery via components oracle is near-optimal","Components oracle matches lower bound up to log factor"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000862,"raw_usage":{"total_tokens":3766,"prompt_tokens":999,"completion_tokens":2767,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":615,"completion_tokens_details":{"reasoning_tokens":2707}},"tokens_in":615,"tokens_out":2767,"duration_ms":19982,"temperature":1.0,"reasoning_tokens":2707,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:27:01.661608+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Optimal graph reconstruction by counting connected components in induced subgraphs","cited_arxiv_id":null,"evidence_quote":"Supplies the edge-counting upper bound that the CC oracle simulates directly, and the non-adaptive $\\Omega(n^2)$ lower bound for the counting oracle that is transferred to CC queries."},{"cited_title":"Graph reconstruction via MIS queries","cited_arxiv_id":null,"evidence_quote":"Provides the randomized query strategy of sampling vertex subsets with controlled inclusion probabilities, plus the witness and query-scheme derandomization used by the bounded-degree algorithms."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the fact that every non-edge of a $k$-tree is separated by a set of exactly $k$ vertices, which drives the bounded-treewidth supergraph construction."},{"cited_title":"The chromatic number of oriented graphs","cited_arxiv_id":null,"evidence_quote":"Supplies the $(k+1)$-coloring fact for bounded-treewidth graphs used to parallelize separator queries by color."},{"cited_title":"Color-coding","cited_arxiv_id":null,"evidence_quote":"Provides the splitter construction that turns randomized query schemes into explicit polynomial-time p-Query-Schemes for derandomization."},{"cited_title":"Fomin, and Pekka Parviainen","cited_arxiv_id":null,"evidence_quote":"Establishes the lower bound on separation queries in terms of maximum pairwise connectivity, which the paper extends to the CC oracle and complements with an $O(\\lambda^2\\log n)$ bound."}],"review_version":2}