{"id":"2dbe74ff-da4c-479d-90bd-e4536d48de10","arxiv_id":"2607.13677","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For k≥3, certifying k-edge-connectivity requires and admits Θ(k log n)-bit labels, while k-vertex-connectivity gets O(k^3√n log^{2.5} n)-bit certificates (unconditionally for k=4, under the Itai–Zehavi conjecture for k≥5).","lead":"This paper determines how many bits of proof each vertex of a network needs to verify, from local checks alone, that the whole network is still connected after k−1 edge or vertex failures. It gives tight logarithmic bounds for k-edge-connectivity, the first certificates for k-vertex-connectivity beyond k=3 (conditional for k≥5), and constant-size certificates for 2-connectivity on sparse networks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Soundness gap in §3 edge-connectivity certification: missing unique-root check allows false acceptance of non-2-edge-connected graphs, breaking Theorem 2 as written.","rationale":"The reader's weakest assumption is the Itai–Zehavi conjecture for k≥5 in Theorem 3. That is a clearly disclosed conditional assumption and does not affect the paper's unconditional results for k-edge-connectivity. The more load-bearing problem is the soundness gap in §3: the certification scheme for Theorem 2, as written, fails to enforce that each certified branching is a single spanning tree rather than a forest with multiple roots. This is not merely a missing detail in the exposition; it produces an actual false acceptance on a 3-vertex path, demonstrating that the scheme is unsound. Since Theorem 2 is a central unconditional claim (the O(k log n) upper bound for k-edge-connectivity), this gap must be fixed before the paper's main contribution can be trusted. The reader did flag this issue in the rationale as 'locally fixable,' but did not make it the weakest assumption, and also flagged a different arithmetic issue in Proposition 1.1 that appears less significant. Therefore I partially agree with the reader: the overall verdict of CONDITIONAL is appropriate, but the binding condition is the §3 unique-root check, not the Itai–Zehavi conjecture. The concrete test isolates the failure and verifies the minimal repair.","tokens_in":31430,"tokens_out":23969,"duration_ms":214153,"concrete_test":"Implement the verification described in §3 and feed the 3-vertex path a-b-c with the malicious certificates above (r=b, two 'trees' with two depth-0 vertices each). If all vertices output accept, soundness is refuted. Then add the rule 'depth_i(v)=0 iff ID(v)=r' and rerun the same instance; if it is now rejected, the missing check is exactly the unique-root condition.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing concern is the soundness gap in the §3 certification scheme for k-edge-connectivity (Theorem 2). The verifier checks root-ID consistency, that each vertex's parent has smaller depth, and that parent IDs at each vertex are distinct among the k branchings. It never checks that exactly one vertex has depth 0. Consequently, a prover can set depth 0 for several vertices, yielding a forest rather than a spanning tree, and the proof's claim that each T_i is an out-branching with n−1 edges is false. This breaks the cut argument: for a cut S not containing r, a forest with a second root inside S may have no arc entering S, so the implied cut-size lower bound fails. The failure is concrete: let G be the 3-vertex path a-b-c (not 2-edge-connected) and set r=b. For two supposed out-branchings T1 and T2, assign T1: a depth 0, b depth 0, c depth 1 with parent b; T2: a depth 1 with parent b, b depth 0, c depth 0. All vertices report root ID b. Depth checks pass; at a the parents are (none,b); at c (b,none); at b (none,none) — all distinct. Every local check passes, so all vertices accept a graph that is not 2-edge-connected. Thus Theorem 2's scheme is unsound as written. The repair is easy (require depth_i(v)=0 iff ID(v)=r, or certify a unique root), and the lower bound is unaffected, but the paper cannot be accepted without this fix.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the local certification of k-edge-connectivity and k-vertex-connectivity. It claims: (i) an O(k log n)-bit certification scheme for k-edge-connectivity via Edmonds' branching theorem and a matching Ω((log n)/k) lower bound for every k≥3, which also applies to k-vertex-connectivity and holds even when vertices see neighbor identifiers and on bounded-degree graphs; (ii) an O(k^3√n log^{2.5} n)-bit scheme for k-vertex-connectivity, unconditional for k=4 and conditional on the Itai–Zehavi conjecture for k≥5; (iii) constant-bit schemes for 2-edge-connectivity in bounded-expansion graphs and for 2-vertex-connectivity in bounded-degree graphs; and (iv) an Ω(log log^* n) lower bound for 2-vertex-connectivity in the anonymous model, together with an Ω(√n) lower bound for certifying independence of two prescribed spanning trees. The lower bounds use cut-and-plug and communication-complexity reductions; the upper bounds use branchings, heavy-light path encodings, Eulerian subgraph covers, and pseudoforest decompositions.","tokens_in":31753,"tokens_out":20118,"duration_ms":167135,"significance":"If the results hold, they resolve BFP24's Open Question 57 for all k≥3 and provide the first local certification schemes for k-vertex-connectivity with k≥4, unconditionally for k=4. The paper also exhibits a sharp complexity dichotomy between k=2 and k≥3 on bounded-degree graphs, and the conditional dependence on the Itai–Zehavi conjecture for k≥5 is clearly disclosed. The techniques are mostly standard and the overall structure is coherent. However, the central upper bound for k-edge-connectivity (Theorem 2) has a soundness gap in its current form, which must be repaired before the main claims can be accepted.","major_comments":[{"comment":"The scheme does not enforce that exactly one vertex has depth_i=0 for each branching T_i. The verification only lets the claimed root r check that depth_i(r)=0; a non-root vertex can set depth_i(v)=0 and no check fails. Thus the proof's assertion that 'every vertex other than the root has exactly one parent' is not validated, and T_i need not be a spanning tree. Concretely, for the 3-vertex path a-b-c with r=b and k=2, set T1: a depth0, b depth0, c depth1 with parent b; T2: a depth1 with parent b, b depth0, c depth0. All root-ID, depth-decrease, and parent-distinctness checks pass, but the graph is not 2-edge-connected. The fix is to add a check that depth_i(v)=0 if and only if ID(v)=r (or equivalently, that every v≠r has a parent with depth exactly one less). The lower bounds and the rest of the paper are unaffected, but Theorem 2 as written is unsound.","section":"Section 3"}],"minor_comments":[{"comment":"The verification rules are written only for out-branchings. The analogous checks for in-branchings should be stated explicitly rather than left to the reader.","section":"Section 3"},{"comment":"The notation Λ_i(u) and the phrase 'T_{-i}-address' are used before being formally introduced; a short definition before the certificate assignment would improve readability.","section":"Section 4.1.1"},{"comment":"The encoding of F via a '*' on the tail of each oriented edge should specify that the orientation is child-to-parent (so that each vertex carries at most one '*' and the pseudoforest convention of Lemma 6.12 is respected). The current wording is ambiguous.","section":"Section 6.1.3, item 1-1"},{"comment":"The caption appears garbled ('Kn+1 n i j'); the figure and its caption should be cleaned up.","section":"Figure 3"},{"comment":"The bounded-degree witness construction is described in one sentence. A precise definition of the graph and of the vertex degrees would make the remark self-contained.","section":"Section 5, Remark 5.2"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is the soundness gap in the §3 branching verifier. Since the repair is straightforward and localized, I recommend major revision rather than rejection. The rest of the paper, including the lower-bound machinery and the k-vertex-connectivity upper bound, appears sound; the conditional status of the k≥5 result is disclosed and reasonable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First: this paper is worth a serious look. It gives the first tight Θ_k(log n) characterization for k-edge-connectivity, answers BFP24's Open Question 57 for k≥3 with an Ω_k(log n) lower bound, and provides the first sublinear certificates for 4-vertex-connectivity (and for k≥5 under Itai–Zehavi). The directed-branching construction is clean, the lower-bound machinery is standard and carefully adapted, and the constant-bit schemes for 2-connectivity on bounded-degree and bounded-expansion classes are a real bonus. If the main theorem holds up, this is a clear advance.\n\nThe bad news is that Theorem 2 as written is not sound. The §3 verifier checks root-identifier consistency, parent depth, and distinct parents, but it never checks that depth_i(v)=0 implies ID(v)=r. So a prover can put several vertices at depth 0. Concrete counterexample: take the path a-b-c and set r=b. In one branching, set depth(a)=0, depth(b)=0, depth(c)=1 with parent b; in the other, set depth(a)=1 with parent b, depth(b)=0, depth(c)=0. All vertices report root b; depth checks pass; parent sets at each non-root are distinct. Every vertex accepts a graph that is not 2-edge-connected. The fix is straightforward—add a check that depth_i(v)=0 iff ID(v)=r—but it has to be made before the theorem can be accepted. The lower bounds are not affected.\n\nI do not share the reader's worry about Proposition 1.1's cut-size count. Read as the number of boundary vertices whose certificates are passed between the two players, 4s+3 is right: the boundary is {p_j}, {a_{i,s}}, v1, v2 on one side and {q_i}, {b_{1,j}}, r on the other. The reduction is the standard one, and the division gives Ω(√n). The statement of Fact 4.5 has a notational slip—for s²-bit inputs it should be Ω(s²), not Ω(s)—but the application uses Ω(s²), so the lower-bound construction is fine.\n\nThe k≥5 vertex-connectivity result depends on the Itai–Zehavi conjecture; that is a genuine caveat, but the paper is explicit about it and the k=4 case is unconditional.\n\nWho should read it: anyone working on distributed verification or proof-labeling schemes. Send it to review, but require the §3 root-check fix and a cleanup of Fact 4.5. The core ideas deserve the referee time.","headline":"Real progress on connectivity certification, but the §3 branching verifier has a soundness hole that must be patched before Theorem 2 can stand.","tokens_in":32299,"tokens_out":15628,"would_cite":true,"duration_ms":156807,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C40","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves tight Θ_k(log n) certificate bounds for k-edge-connectivity and gives the first local certification schemes for k-vertex-connectivity with k≥4, at Õ_k(√n) bits under a long-standing conjecture.","keywords":["local certification","proof-labeling schemes","edge connectivity","vertex connectivity","branching theorem","independent spanning trees","heavy-light decomposition","bounded-expansion graphs"],"falsifier":"Construct a single 5-vertex-connected graph with a distinguished root r that fails to contain five independent spanning trees rooted at r. Such a graph would disprove the conjecture on which the k≥5 upper bound rests, so the stated Õ(√n)-bit certificate for k=5 would not follow.","tokens_in":31287,"feed_emoji":"🕸️","tokens_out":8530,"duration_ms":65641,"temperature":0.7,"pith_summary":"Local certification asks how many bits a centralized prover must attach to each vertex so that every vertex, by checking only its own label and its neighbors' labels, can be certain that the whole graph has a global property. This paper establishes tight bounds for connectivity certification: for k-edge-connectivity with k≥3, Θ_k(log n) bits per vertex are both necessary and sufficient, settling a long-standing open question in the area for all k≥3. For k-vertex-connectivity with k≥4, it supplies the first certification schemes, with O(k^3 √n log^{2.5} n)-bit labels, unconditional for k=4 and conditional on the independent-spanning-trees conjecture for larger k. It also proves a sharp contrast at k=2: on bounded-degree and bounded-expansion graphs, 2-connectivity can be certified with constant-size labels, while in the anonymous model 2-vertex-connectivity needs a super-constant number of bits. Together these results map the cost of making a network's robustness locally verifiable.","feed_headline":"Tight bound: Θ(log n) bits certify k-edge-connectivity","feed_subtitle":"New schemes certify 4-vertex-connectivity locally; a long-standing conjecture separates √n from log n.","key_machinery":"The proof rests on three mechanisms: (1) the classical branching theorem, which lets k-arc-strong connectivity of the bidirected graph be witnessed by two collections of k pairwise arc-disjoint spanning branchings, so each vertex need only check parent and depth fields; (2) the independent-spanning-trees characterization of k-vertex-connectivity, combined with heavy-light decompositions that encode root-to-vertex paths by O(log n) segment-rank pairs, letting a vertex locally detect a common internal ancestor in two trees; and (3) the cut-and-plug lower-bound construction, in which two copies of a k-connected witness graph with a low-degree edge are rewired to produce a graph of connectivity","core_discovery":"The central discovery is that k-edge-connectivity admits a local certification scheme with O(k log n)-bit labels for every k≥2, and that for k≥3 any such scheme requires Ω((log n)/k) bits — even when vertices see their neighbors' identifiers — yielding a tight Θ_k(log n) characterization and a positive answer to the open question of whether Ω(log n) is necessary. The upper bound works by orienting each edge both ways and invoking the classical branching theorem for arc-disjoint branchings: certifying k arc-disjoint out-branchings and k in-branchings rooted at a common vertex, each locally checkable through parent/depth certificates. For vertex connectivity, the paper uses the conjecture that","pith_inferences":["If the independent-spanning-trees conjecture fails for some k≥5, the stated Õ_k(√n)-bit certificate for that k would not follow; the unconditional k=4 result would survive, but the 'for all k' claim in the vertex-connectivity theorem would collapse. The conjecture is the single load-bearing assumption for that upper bound.","The lower-bound construction's rewiring yields only connectivity 2, which explains why the k=2 case escapes logarithmic lower bounds; finding witnesses whose rewiring preserves k−1 connectivity would raise the vertex-connectivity lower bound toward √n and match the new upper bound.","The heavy-light path-encoding technique is a reusable tool: any property expressible as 'no common ancestor in two rooted trees' can likely be certified in Õ(√n) bits, opening a route to certifying other tree-based structures such as dominator trees or sparsest cuts.","The paper's approximate-certification discussion implies that distinguishing k-connected from (k−2)-connected graphs retains the logarithmic lower bound, while a connected-dominating-set decomposition certifies only weaker connectivity in O(k log n) bits — so approximation may deliver large savings in label size if exact vertex-connectivity certification turns out to require √n."],"forward_implications":["Resolves the previous open question for k≥3: any local certification scheme for k-vertex- or k-edge-connectivity needs Ω(log n) bits, so the logarithmic barrier cannot be beaten in general.","Gives the first local certification schemes for k-vertex-connectivity with k≥4, with the 4-vertex-connectivity case unconditional at O(√n log^{2.5} n) bits.","Establishes a sharp k=2 versus k≥3 separation: bounded-degree graphs admit constant-size certificates for 2-edge- and 2-vertex-connectivity, while k≥3 requires logarithmic labels even on bounded-degree graphs.","Shows the independent-trees building block is essentially optimal: certifying that two prescribed spanning trees are independent requires Ω(√n) bits, matching the Õ(√n) upper bound up to log factors.","Extends constant-size anonymized certification to bounded-expansion graph classes for 2-edge-connectivity, a family that includes planar and minor-closed graph classes."],"fun_headline_variants":["Tight Θ(log n) certification for k-edge-connectivity","k-edge-connectivity: log n bits exactly","Sparse graphs: constant-size local certificates for 2-connectivity","Lower bound: Ω(log n) bits for k-connectivity certification"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"For the upper bound on k-vertex-connectivity with k≥5, the load-bearing assumption is the independent-spanning-trees conjecture — that k-vertex-connectivity is equivalent to the existence of k independent spanning trees rooted at every vertex; if that conjecture is false for some such k, the stated bound for that k does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Tight Θ(log n) certification for k-edge-connectivity","k-edge-connectivity: log n bits exactly","Sparse graphs: constant-size local certificates for 2-connectivity","Lower bound: Ω(log n) bits for k-connectivity certification"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000255,"raw_usage":{"total_tokens":1500,"prompt_tokens":925,"completion_tokens":575,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":669,"completion_tokens_details":{"reasoning_tokens":501}},"tokens_in":669,"tokens_out":575,"duration_ms":5955,"temperature":1.0,"reasoning_tokens":501,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T04:29:31.789794+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a single 5-vertex-connected graph with a distinguished root r that fails to contain five independent spanning trees rooted at r. Such a graph would disprove the conjecture on which the k≥5 upper bound rests, so the stated Õ(√n)-bit certificate for k=5 would not follow.","supporting_citations":[],"review_version":1}