{"id":"c178f782-46fb-481e-accf-6023bf7c9a72","arxiv_id":"2506.08405","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Counting connected components in induced subgraphs reconstructs any n-node m-edge graph with Θ(m log n / log m) adaptive queries, while non-adaptive algorithms need Ω(n²).","lead":"This paper studies how many queries of the form 'how many connected components does this induced subgraph have?' are needed to reconstruct an unknown graph. It proves tight bounds, shows non-adaptive queries are hopeless, and gives a two-round algorithm.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.3's edge test 'CC(U)=CC(U∪{v})' is false when v touches ≥2 components of G[U], so the binary-search subroutine used via Corollary 3.8 in Theorem 1.1 can silently miss all of v's edges.","rationale":"I reviewed the proof of Theorem 1.1 and its supporting machinery in good faith. The reader's weakest assumption is exactly the most load-bearing flaw I found: Lemma 2.3's false equivalence. I verified the counterexample and traced the dependence: Lemma 2.3 is used only through Corollary 3.8, which handles the i ≥ 2 stages of the main proof, so without a fix the adaptive upper bound is unproven. The fix (compare CC(U∪{v}) with CC(U)+1, i.e., two queries per test) is cost-preserving, so the Θ(m log n/log m) claim is very likely correct; the paper is a conditional accept. I checked the rest of the machinery and found no further fatal flaw. Lemmas 3.1-3.6 (random subgraph sampling and forest reconstruction) are sound: the good-event analysis in Claims 3.3-3.4 is correct and the Jensen steps go through. The degree-level decomposition in Section 3.3 is coherent, and the case analyses for edges inside Si ∪ Si+1 and between far-apart levels are algebraically consistent. Both lower bounds (Theorems 1.2 and 1.3) appear correct: the non-adaptive argument that only singleton-pair queries distinguish the two path-graph candidates is clean, and the adaptive Ω(m) reduction from unstructured search for m ≥ n is sound. The two-round algorithm has a separate small gap: in Lemma 4.1, Claim 4.3's assertion µp ≥ 1/e fails when d = (n−1)/2 (µp = 1/4 < 1/e), and for d ≳ 0.571(n−1) no tested p satisfies Zp > 1/(2e), so p* may be undefined for very high-degree vertices; since Theorem 1.4 is not the central claim, I treat this as secondary. I also confirm the reader's secondary point that the final verification step of Theorem 1.1 assumes |E| = m rather than the stated upper bound. Because both central-claim gaps are real but localized and patchable without changing the asymptotic result, I keep the reader's CONDITIONAL verdict.","tokens_in":21573,"tokens_out":41263,"duration_ms":433903,"concrete_test":"Run the Lemma 2.3 binary search on the 3-vertex path G = ({v,a,b}, {(v,a),(v,b)}) with K = ∅. For vertex v with Uv = {a,b}, the lemma's test evaluates CC({a,b}) = 2 vs CC({a,b,v}) = 1 and concludes 'no edge between v and Uv', halting without outputting either edge, which refutes the lemma as written and shows Corollary 3.8 inherits the failure. Then re-run with the corrected test CC(U∪{v}) ≤ CC(U): the initial check passes (1 ≤ 2), the two singleton halves {a} and {b} each return edges (v,a) and (v,b), confirming the patch restores correct reconstruction with the same two-query-per-test cost and unchanged asymptotic bounds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 2.3 claims that for U ⊆ V\\{v}, v has an edge to U iff CC(U) = CC(U∪{v}). Adding v merges the k ≥ 0 components of G[U] containing neighbors of v, giving CC(U∪{v}) = CC(U) − k + 1. Equality holds exactly when k = 1; if k ≥ 2 the counts differ although an edge exists, and if k = 0 they differ by +1. The reader's example (U = {a,b} independent, v adjacent to both, CC(U)=2, CC(U∪{v})=1) is correct. The binary search in Lemma 2.3 uses this test to decide whether to recurse and otherwise halts, so whenever a vertex's neighbors lie in ≥2 components of the current set, the subroutine reports no edges and drops all of them. Lemma 2.3 is invoked in Corollary 3.8 after Lemma 3.1 reduces the remaining edge count, and Corollary 3.8 is the i ≥ 2 'reconstruct edges inside Si ∪ Si+1' stage of Theorem 1.1, so the main adaptive upper bound is unproven as written. The patch is immediate and cost-preserving: the correct test is CC(U∪{v}) < CC(U)+1 (equivalently CC(U∪{v}) ≤ CC(U)), costing two CC-queries per comparison, so the asymptotic O((n+m_u)·log(n²/(n+m_u))) bound of Lemma 2.3 is unchanged. A second, smaller gap is the final verification step of Theorem 1.1: it accepts only when the number of discovered edges equals the input m, which the statement gives only as an upper bound, so graphs with fewer than m edges would loop forever; the theorem needs exact m or a different boosting argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a graph reconstruction model in which a query returns the number of connected components of an induced subgraph. The main claims are: an adaptive algorithm with optimal expected query complexity Θ(m log n / log m) for n-node m-edge graphs; an Ω(n^2) lower bound for non-adaptive algorithms even when the graph has only O(n) edges; and a two-round algorithm using O(m log n + n log^2 n) queries. The adaptive upper bound is built from a forest-reconstruction subroutine that simulates additive queries through CC queries, a randomized matching-sampling routine, and a degree-threshold decomposition of the vertex set. The lower bounds use information-theoretic counting and a reduction from unstructured search.","tokens_in":21948,"tokens_out":19651,"duration_ms":231571,"significance":"If the results hold, they settle the adaptive query complexity of CC-query reconstruction and establish a strong separation between adaptive and non-adaptive algorithms, as well as a contrast with additive and cross-additive query models. The non-adaptive lower bound is clean and robust, and the two-round algorithm is an elegant application of group testing. However, the main adaptive upper bound currently rests on an incorrect edge-detection equivalence in Lemma 2.3, and the proof's final verification step assumes exact knowledge of the edge count even though the theorem statement allows only an upper bound. Both issues are identifiable, local, and appear repairable without changing the claimed rates.","major_comments":[{"comment":"The edge-detection equivalence stated in the proof is false: the text claims that for any U ⊆ V \\ {v}, there is at least one edge between v and U if and only if CC(U) = CC(U ∪ {v}). If v has neighbors in k ≥ 2 distinct connected components of G[U], then CC(U ∪ {v}) = CC(U) − k + 1, so the counts are unequal even though an edge exists. For example, with U = {a,b} independent and v adjacent to both, CC(U) = 2 and CC(U ∪ {v}) = 1. Since the binary-search subroutine halts when this test reports no edge, it can silently miss all edges from v to such a U. Lemma 2.3 is subsequently used in Corollary 3.8 and hence in the main adaptive algorithm of Theorem 1.1, so the upper bound is unproven as written. The fix is to test the correct condition CC(U ∪ {v}) < CC(U) + 1 (equivalently CC(U ∪ {v}) ≤ CC(U)), which costs two CC-queries per comparison and preserves the asymptotic O((n + m_u) log(n^2/(n + m_u))) bound.","section":"Section 2.1, Lemma 2.3"},{"comment":"The final verification and boosting step accepts a proposed reconstruction only when the number of discovered edges equals the input m. This treats m as the exact edge count, but Theorem 1.1 is stated for an upper bound m on the number of edges. For a graph with m' < m actual edges, a run that has correctly found every edge will have |K| = m' ≠ m, so the test never passes and the algorithm loops forever; consequently the expected query complexity is not finite. The theorem should either be restated with exact m as input, or the algorithm must be given a stopping rule that certifies completeness without knowing the exact edge count, for example by running a corrected Lemma 2.3 to completion and verifying only that no false edges are output.","section":"Section 3.3, proof of Theorem 1.1"}],"minor_comments":[{"comment":"The displayed final bound 'O(m log m / log n)' should read 'O(m log n / log m)'.","section":"Section 3.3, last line of Theorem 1.1 proof"},{"comment":"The phrase 'reconstructs the whoel graph' contains a typo; it should be 'whole graph'.","section":"Section 2.1, before Lemma 2.3"},{"comment":"The claim that a CC-query 'returns at most log(m + 1) bits of information' deserves a one-line justification: for any fixed query set U, the answer CC(U) lies in an interval of length at most m + 1 because CC(U) is between |U| − m and |U|.","section":"Section 5.2, first paragraph"},{"comment":"The vector notation switches between x_u in Lemma 4.4 and v in Lemma 4.5; please align the notation so that the support of the vector is unambiguously the neighbor set of the queried vertex.","section":"Section 4, Lemmas 4.4 and 4.5"}],"recommendation":"major_revision","confidential_remarks":"The core flaw in Lemma 2.3 is genuine but local, and the proposed two-query fix preserves the stated complexity. The exact-m versus upper-bound issue in Theorem 1.1 is also fixable, either by restating the theorem with exact m or by adding a completeness-certifying final step. If the authors address both points, I would expect the central claims to be salvageable; the lower-bound sections appear sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline. The paper introduces a new query model — count connected components of an induced subgraph — and proves tight adaptive bounds, a strong non-adaptive lower bound, and a two-round algorithm. The main adaptive upper bound as written is wrong: Lemma 2.3 uses an incorrect equivalence that can silently miss all of a vertex's edges. The fix is immediate and does not change the asymptotic bound.\n\nThe good. This is the first study of CC-queries for graph reconstruction. The lower bounds are clean information-theoretic arguments that look correct. The two-round algorithm is a nice combination of degree estimation (Lemma 4.1) with group testing, and it's independently interesting that two rounds beat non-adaptive queries so dramatically. The forest-reconstruction trick (simulating density queries with CC queries) is clever.\n\nThe soft spots. Lemma 2.3 claims that v has an edge to U iff CC(U)=CC(U∪{v}). This is false when v has neighbors in two or more components of G[U]: adding v merges those components, so CC drops. The binary search then thinks there is no edge and halts, losing all of v's edges. Corollary 3.8 and the i≥2 stage of Theorem 1.1 depend on this lemma. The patch is to test whether CC(U∪{v}) < CC(U)+1 (equivalently CC(U∪{v}) ≤ CC(U)), which costs two CC-queries per comparison, so Lemma 2.3's O((n+mu) log(...)) bound is preserved. A second, smaller gap: Theorem 1.1's verification step expects to find exactly m edges, but m is an upper bound; a graph with fewer edges would loop forever. That needs an exact m or a different stopping rule. Also, Fact 4.2 misstates the effect of adding u to S: when u touches multiple components, CC(S∪{u})−CC(S) is negative, not 0. The degree-estimation algorithm only needs to check whether the difference is 1, so this is a typo rather than a fatal flaw.\n\nOverall: the lower bounds and the two-round algorithm stand on their own. The adaptive upper bound is plausible and likely correct after the trivial patch, but the proof as written is not.\n\nWho this is for: anyone working on graph reconstruction, query complexity, or oracle models. It deserves a serious referee; I'd send it to review with a note asking the authors to fix the edge test and the m/exactness issue. I would also bring it to the reading group.","headline":"New CC-query model with tight bounds, but the main adaptive proof has a false edge test; the fix is trivial and the rest holds.","tokens_in":22485,"tokens_out":5751,"would_cite":true,"duration_ms":64502,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Counting connected components in vertex subsets is enough to rebuild any graph, and the number of queries needed is now known exactly.","keywords":["graph reconstruction","connected components","query complexity","adaptive algorithms","non-adaptive lower bounds","group testing","induced subgraph queries","forest sampling"],"falsifier":"On the four-vertex graph with vertices a, b, c, v and edges a-c, c-b, v-a, v-b, query U = {a, b} and U ∪ {v}: the oracle returns CC(U) = 2 and CC(U ∪ {v}) = 1, so the Lemma 2.3 equivalence 'there is an edge between v and U iff CC(U) = CC(U ∪ {v})' is false. Running the binary-search subroutine from Lemma 2.3 on this graph would therefore either miss the edges (v, a) and (v, b) or exceed the claimed query bound, exposing the load-bearing premise.","tokens_in":21376,"feed_emoji":"🔍","tokens_out":5840,"duration_ms":69276,"temperature":0.7,"pith_summary":"The paper asks how many times an oracle must be asked how many connected components a vertex subset induces in order to fully reconstruct a hidden graph. It settles the question with matching upper and lower bounds: every n-node m-edge graph can be recovered adaptively with O(m log n / log m) queries in expectation, and no adaptive randomized algorithm can do better. The same query model is far weaker without adaptivity: any non-adaptive algorithm needs Ω(n²) queries even when the graph has only O(n) edges. A two-round algorithm with O(m log n + n log² n) queries interpolates between these extremes. The result pinpoints the exact power of one of the most basic graph statistics as a query primitive.","feed_headline":"Component-count queries rebuild graphs in Θ(m log n / log m) queries","feed_subtitle":"Adaptive algorithms match the lower bound; one-shot algorithms need Ω(n²) queries even for sparse graphs.","key_machinery":"The load-bearing identity is that on any forest, the number of edges in an induced subgraph equals |U| − CC(U), so one CC-query can simulate one edge-density query. The adaptive algorithm samples vertex subsets at probability p = Θ((mD)^−1/3) so that the induced subgraph is a matching (hence a forest) with constant probability, discovers edges there using a forest-reconstruction subroutine, and repeats with the discovered edges removed. The binary-search edge test — adding a vertex to a set leaves the component count unchanged exactly when the vertex has a neighbor in that set — is used to recover leftover edges when few remain. The two-round algorithm first estimates every vertex's degree by sampling random subsets and checking whether the component count changes, then recovers each neighborhood by group testing, where each OR-query is simulated by two CC-queries. Forest reconstruction itself relies on a prior density-query reconstruction algorithm, simulated one-for-one on induced subgraphs.","core_discovery":"The central claim is that the number of connected components in induced subgraphs gives a graph reconstruction model with query complexity Θ(m log n / log m) for adaptive algorithms, for every value of m. The upper bound is proved by an algorithm that alternates between reconstructing edges inside similar-degree vertex sets — by randomly sampling induced subgraphs that become matchings, so that one CC-query simulates one edge-count query on a forest — and reconstructing edges between very different-degree sets by coloring and applying a forest-reconstruction subroutine. The matching lower bound is proved by an information-theoretic counting argument for sparse graphs and, for dense graphs, by reducing from unstructured search on the missing edge of an almost-complete graph. A separate lower bound shows that non-adaptive algorithms require Ω(n²) queries even for graphs with O(n) edges, and a two-round algorithm achieves O(m log n + n log² n) queries in the worst case.","pith_inferences":["If the binary-search edge test could be made robust to vertices that touch multiple components of the queried set, the same Θ(m log n / log m) upper bound would extend to noisy or approximate CC-query models.","The degree-estimation routine — sampling random subsets and checking whether the component count changes — could plausibly be adapted to estimate other monotone graph statistics, such as the total number of edges, using only CC-queries.","The lower-bound graphs, which are unions of 2-paths plus one optional chord, may transfer to other query models where a single query can distinguish only pairs that are both contained in the queried set.","The exact agreement with the weighted-additive query bound raises the question of whether CC-queries can simulate weighted edge-count queries in general, or whether the similarity is coincidental to the forest case."],"forward_implications":["Adaptive CC-queries are optimal for every m, matching the weighted-additive query bound and beating IS-queries whenever ω(1) < m < n^{2−ε}.","Non-adaptive algorithms are essentially forced to query quadratically many sets even on sparse graphs, so adaptivity yields a separation from near-linear to quadratic query cost.","A two-round algorithm with O(m log n + n log² n) queries shows that most of the benefit of adaptivity can be captured in a single extra round, though the exact two-round optimum is left open.","The non-adaptive lower-bound construction, based on graphs built from length-2 paths, shows that any one-round algorithm must in effect ask about every pair of vertices.","The forest-simulation technique gives a general template for transferring density-query algorithms into the CC-query model."],"supporting_citations":[{"why":"Supplies the density-query reconstruction algorithm (Theorem 2.1) that CC-queries simulate on forests; this is the core of Lemma 2.2 and the adaptive algorithm.","marker":"[Maz10]"},{"why":"Supplies the non-adaptive group-testing lemma (Lemma 4.5) used to recover each neighborhood in the two-round algorithm.","marker":"[BLMS24]"},{"why":"Gives the O(m log n) IS-query reconstruction algorithm against which the CC-query bound is compared and shown to improve.","marker":"[AC08]"},{"why":"Establishes the optimal additive-query bound Θ(m log(n²/m)/log m) that provides the comparison point for dense graphs.","marker":"[CK10]"},{"why":"Proves the non-adaptive IS-query lower bound that Theorem 1.3 complements and contextualizes.","marker":"[AB19]"}],"fun_headline_variants":["Adaptive component-count queries hit Θ(m log n / log m) complexity","Non-adaptive component queries need Ω(n²) even for sparse graphs","Two-round algorithm uses O(m log n + n log² n) queries","Component-count oracle yields optimal adaptive reconstruction","Optimal graph reconstruction via component-count queries"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The adaptive algorithm's binary-search edge test assumes that adding a vertex to a set of vertices changes the component count exactly when the vertex has no neighbor in that set, but this equivalence fails when the vertex has neighbors in two different components of the set, because then the count drops instead of staying level.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive component-count queries hit Θ(m log n / log m) complexity","Non-adaptive component queries need Ω(n²) even for sparse graphs","Two-round algorithm uses O(m log n + n log² n) queries","Component-count oracle yields optimal adaptive reconstruction","Optimal graph reconstruction via component-count queries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001149,"raw_usage":{"total_tokens":4732,"prompt_tokens":879,"completion_tokens":3853,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":495,"completion_tokens_details":{"reasoning_tokens":3768}},"tokens_in":495,"tokens_out":3853,"duration_ms":32469,"temperature":1.0,"reasoning_tokens":3768,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:15:15.338179+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On the four-vertex graph with vertices a, b, c, v and edges a-c, c-b, v-a, v-b, query U = {a, b} and U ∪ {v}: the oracle returns CC(U) = 2 and CC(U ∪ {v}) = 1, so the Lemma 2.3 equivalence 'there is an edge between v and U iff CC(U) = CC(U ∪ {v})' is false. Running the binary-search subroutine from Lemma 2.3 on this graph would therefore either miss the edges (v, a) and (v, b) or exceed the claimed query bound, exposing the load-bearing premise.","supporting_citations":[],"review_version":1}