{"id":"e75e562c-4aaf-4dc4-9f1b-61f61c90fa97","arxiv_id":"2502.00951","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Tree-length is within constant factors of bramble interception radius, Helly-family interception radius, same-vertex-set additive tree distortion, and two new cycle bridging parameters.","lead":"This paper proves that many different ways of measuring how close a graph is to a tree are equivalent up to constant factors, including new measures based on brambles and cycle shortcuts. For algorithm designers, any graph with one small measure is guaranteed to have small tree-length, so algorithms for tree-like graphs transfer automatically.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Coarse-equivalence definition clashes with parameters vanishing on trees: no β satisfies tl ≤ β·q for q∈{adt,bnc,mcw,ph,sh,Δs,ρs} on any tree.","rationale":"The reader's weakest_assumption concerned the reliability of quoted inequalities such as Proposition 5. That is not where the central problem lies. The more serious issue is that the paper's formal definition of coarse equivalence is multiplicative, while several of the parameters listed in the central claim are identically zero on trees, where tree-length equals 1. For example, adt(P3)=0 and tl(P3)=1, so no universal constants α, β > 0 can satisfy α·adt ≤ tl ≤ β·adt for all graphs. The same holds for bnc, mcw, ph, sh, Δs, ρs, ad, glc, and mf. The paper's own inequalities are mostly additive (e.g., tl ≤ 2·adt+1, (tl−1)/2 ≤ adt), which prove that boundedness of one parameter is equivalent to boundedness of tree-length, but they do not establish the stated constant-factor equivalence. This is not a matter of an off-by-one constant in a single theorem; it affects the interpretation of the main result and the abstract. The mathematics supporting boundedness equivalence appears sound, and the fix is conceptually simple: either redefine coarse equivalence with additive slack, or state the result for shifted parameters such as q+1. Because the central claim as written is false, the paper should not be accepted in its current form; a conditional acceptance requiring the definition and claims to be aligned seems appropriate. This concern is distinct from the reader's identified weakest assumption, so I disagree with that assessment.","tokens_in":31104,"tokens_out":33541,"duration_ms":317938,"concrete_test":"Take G = P3, the path on three vertices a-b-c. Compute tl(G) = 1, adt(G) = 0, bnc(G) = 0, mcw(G) = 0, ph(G) = 0, sh(G) = 0, Δs(G) = 0. The multiplicative inequality tl(G) ≤ β·adt(G) becomes 1 ≤ 0, impossible for any β > 0. This single example falsifies the claimed pairwise constant-factor equivalence between tree-length and each of these parameters. The same test works with any tree and with ad, bnc, mcw, ph, sh, Δs, ρs.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 1 defines two parameters as coarsely equivalent if there exist universal constants α, β > 0 with α·q(G) ≤ p(G) ≤ β·q(G) for every graph G. This definition is incompatible with the paper's central claim for any parameter that is 0 on trees while tree-length is 1. For a 3-vertex path P3, tl(P3) = 1, but Δs(P3) = ρs(P3) = adt(P3) = ad(P3) = bnc(P3) = mcw(P3) = ph(P3) = sh(P3) = glc(P3) = mf(P3) = 0. Hence no positive β can satisfy tl(P3) ≤ β·q(P3) for these q. The paper's theorems actually establish additive bounds, e.g., Lemma 7 (tl ≤ 2·adt + 1) and Corollary 4 ((tl−1)/2 ≤ adt), which imply boundedness equivalence but not multiplicative coarse equivalence. The abstract's new results for Helly-family interception parameters ph and sh, and for additive tree embedding adt, are therefore not 'within constant factors' of tree-length under the formal definition. The flaw is not in the individual proofs but in the match between the stated definition and the claimed conclusion.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies graph parameters that are claimed to be coarsely equivalent to tree-length. It recasts several known results in a unified layering-partition framework, giving simpler proofs and sometimes improved constants for the bottleneck constant, McCarty-width, K-fat K3-minors, and additive tree embeddings, and it introduces new parameters: bramble and Helly-family interception radii (br, sh, ph), additive distortion to an unweighted tree on the same vertex set (adt), and two cycle bridging constants (cbc, bgc). The main results are explicit two-sided inequalities relating these parameters to tl(G) and tb(G), showing that boundedness of any one parameter is equivalent to bounded tree-length.","tokens_in":31368,"tokens_out":17414,"duration_ms":161407,"significance":"If the framing is corrected, the paper is a useful contribution. It provides a coherent set of explicit inequalities, simplifies and extends known proofs, improves several constants, and proposes new boundedness characterizations that are natural and likely to be useful in algorithmic applications and in further structural work. The paper is mostly self-contained, and the inequalities are stated with explicit constants. The substantive content—the additive inequalities and the resulting boundedness equivalences—appears sound, but the formal claim of multiplicative coarse equivalence is not.","major_comments":[{"comment":"The definition of coarse equivalence in Section 1 requires universal constants α, β > 0 with α·q(G) ≤ p(G) ≤ β·q(G) for every graph G. This is incompatible with the paper's own inequalities for parameters that vanish on trees. For the 3-vertex path P3, tl(P3) = 1, while Δs(P3) = ρs(P3) = adt(P3) = bnc(P3) = mcw(P3) = ph(P3) = sh(P3) = glc(P3) = mf(P3) = 0. Hence no positive β can satisfy tl(P3) ≤ β·q(P3) for any of these q. The theorems therefore do not establish 'within constant factors' in the formal sense; they establish boundedness equivalence with additive constants, e.g., Corollary 4 gives (tl−1)/2 ≤ adt(G) ≤ 3·tl(G), Theorem 2 gives mcw(G) ≤ tb(G) ≤ tl(G) ≤ 6·mcw(G)+1, and Proposition 15 gives mcw(G) ≤ ph(G) ≤ sh(G) ≤ br(G) ≤ tb(G). The abstract, introduction, and conclusion should be reworded to state boundedness equivalence, or the definition of coarse equivalence should be modified to allow additive constants; the current wording is mathematically false as written.","section":"Section 1; Theorem 2; Theorem 3; Corollary 4; Proposition 15"},{"comment":"The displayed chain 'mf(G) ≤ 2·bnc(G)+1 ≤ Δs(G)+1 ≤ 5·mf(G)' is false as stated for arbitrary s. Let G be the 4-cycle with one chord, i.e., vertices 0,1,2,3 and edges 01,12,23,30,02. For s = 1, the layering partition has layer 1 equal to {0,2}, which forms one cluster of diameter 1, so Δ1(G) = 1. The bottleneck constant is bnc(G) = 1: the pair (1,3) has distance 2 with two shortest paths, 1-0-3 and 1-2-3; their middle vertices 0 and 2 are at distance 1, and no radius 0 works. Thus 2·bnc(G)+1 = 3 > 2 = Δ1(G)+1. The cited ingredients (Lemma 1 and Corollary 1) give only bnc ≤ 3/2·Δs, which yields 2·bnc ≤ 3·Δs, not 2·bnc ≤ Δs. This step needs to be repaired or the constants in Theorem 4 changed.","section":"Theorem 4"}],"minor_comments":[{"comment":"The proof says 'applying Lemma 5 three times', but Lemma 5 is the balanced clique-separator lemma for chordal graphs; the intended reference appears to be Lemma 8, the distance-approximating tree lemma.","section":"Corollary 5"},{"comment":"There is a typo in the notation 'dG(S1.S2)'; it should be 'dG(S1, S2)'.","section":"Section 2.1"},{"comment":"The list of parameters in the introduction includes glc(G), but the paper gives no new bounds for glc(G) beyond the quoted Proposition 14 from [9]. The text should clarify which parameters receive new proofs versus which are only cited, to avoid implying that glc is treated here.","section":"Introduction and Conclusion"}],"recommendation":"major_revision","confidential_remarks":"The definitional mismatch is pervasive but fixable: the real theorems are boundedness equivalences with additive constants, and those appear correct. The false inequality in Theorem 4 is local and should be repairable by adjusting constants or the quantification over s. I would not recommend rejection; the paper is within scope and the corrected version would be a useful reference."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The stress-test note is right, and it matters. The paper defines coarse equivalence multiplicatively: there must be constants α, β > 0 with αq ≤ p ≤ βq for every graph. But on any tree with at least one edge, tl = 1 while Δs, ρs, adt, bnc, mcw, ph, and sh are all 0. So no β satisfies tl ≤ β·q. The theorems in the paper actually prove additive bounds, e.g., (tl−1)/2 ≤ adt ≤ 3tl, which give boundedness equivalence but not the multiplicative constant-factor equivalence claimed in the abstract and in Section 4. This is not a flaw in the individual proofs; it's a mismatch between the stated definition and the conclusions drawn from it.\n\nThat said, there is real substance here. The bramble interception radius, the Helly-family interception radii, the same-vertex-set additive tree distortion adt, and the cycle bridging constants cbc and bgc are genuinely new parameters. The layering-partition proofs are simpler than the earlier arguments in [9,44] and sometimes give better constants, which is a concrete contribution. The paper also works as a useful unified survey of the area, and the appendix glossary helps navigate the many parameters.\n\nThe soft spots are the definitional issue, which is load-bearing for the abstract's claims, and a couple of inequality chains that are stated without full derivation—the reader flagged the step (2bnc+1 ≤ Δs+1) in Theorem 4, and that deserves a careful check. Neither of these makes me suspect the underlying results are wrong; the additive bounds are what is needed for the algorithmic applications anyway.\n\nWho is this for? Anyone working on tree-length, tree-breadth, or graph parameters that behave like tree metrics. It deserves a serious referee, but the author should be required to correct the coarse-equivalence definition or restate the results as boundedness equivalences. As written, the central claim is overstated, and the paper should not be accepted without that fix.","headline":"The proofs are mostly solid, but the paper's central claim of multiplicative coarse equivalence is false under its own definition because parameters like adt and bnc vanish on trees while tree-length is 1.","tokens_in":31853,"tokens_out":4721,"would_cite":true,"duration_ms":50928,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C62"],"pacs":[],"model":"deepseek-v4-flash","headline":"A graph's tree-length is bounded exactly when eighteen related parameters are bounded.","keywords":["coarse equivalence","tree-length","tree-decomposition","layering partition","bramble","Helly family","distance-approximating tree","cycle bridging property"],"falsifier":"Take a chordal graph (tree-length 1) with unbounded clique size and compute the bramble interception radius $br(G)$: the theorem predicts $br(G) \\leq 1$, so any chordal graph whose brambles require a disk of radius 2 or more would refute the claimed coarse equivalence between $br$ and tree-breadth.","tokens_in":2034,"feed_emoji":"🌳","tokens_out":3014,"duration_ms":116987,"temperature":0.7,"pith_summary":"Tree-length measures how tree-like a graph is: it is the smallest possible maximum diameter of a bag in a tree-decomposition. The paper's central claim is that tree-length and a family of eighteen graph parameters are coarsely equivalent, meaning each parameter is trapped between a constant multiple of tree-length and a constant multiple of the others for every graph. The new parameters added to this list include the radius of a single disk needed to pierce every bramble, every Helly family of connected subgraphs, or every Helly family of paths, and the smallest distortion with which the graph's own vertex set can be embedded into an unweighted tree. The paper also introduces a cycle bridging constant and shows it sits on the same scale. A sympathetic reader should care because any algorithm, bound, or structural fact that holds for bounded tree-length automatically transfers to every graph with any of these parameters bounded, and several of them are much easier to compute or certify.","feed_headline":"Eighteen graph parameters collapse into one tree-length scale","feed_subtitle":"Bounded tree-length now means brambles, Helly families, and cycle bridges are bounded too.","key_machinery":"The load-bearing object is the layering partition of a graph with respect to a start vertex, together with its cluster-diameter $\\Delta_s(G)$, the largest metric diameter of a cluster in that partition. The paper uses the previously established sandwich $\\Delta_s(G)/3 \\leq tl(G) \\leq \\Delta_s(G)+1$ to translate every new or old parameter bound into a tree-length bound, and it repeatedly converts combinatorial witnesses (a bramble, a Helly family, a path avoiding a disk, a cycle failing a locality condition) into two vertices in one cluster, bounding their distance by $\\Delta_s(G)$. A second workhorse is the canonical tree built from a layering partition, which shows that a small cluster-diameter yields an additive approximation of graph distances by an unweighted tree on the same vertex set, and conversely Lemma 7 turns a distance-approximating tree into a tree-decomposition via powers of trees, which are chordal graphs.","core_discovery":"On the paper's own terms, the discovery is that the list $\\{tl, tb, itl, itb, \\Delta_s, \\rho_s, td, ad, adt, bnc, mcw, ph, sh, br, mf, glc, cbc, bgc\\}$ forms a single coarse equivalence class: for every graph $G$, any two of these parameters are within small universal constant factors of each other, so boundedness of any one of them is equivalent to bounded tree-length. The new equivalences are stated as sandwich inequalities: for example, $(tl(G)-1)/2 \\leq adt(G) \\leq 3\\,tl(G)$ for distance-approximating trees on the same vertex set, $mcw(G) \\leq ph(G) \\leq sh(G) \\leq br(G) \\leq tb(G) \\leq tl(G) \\leq 6\\,mcw(G)+1$ for disk interception of brambles and Helly families, and $\\frac{2}{3}(cbc(G)-1) \\leq tl(G) \\leq 4\\,cbc(G)+3$ for the cycle bridging constant. Earlier results on bottleneck constant, McCarty-width, $K_3$-minor fatness, and geodesic loaded cycles are reproved with simpler, more direct arguments and, in several cases, improved constants.","pith_inferences":["If the equivalence class is as robust as claimed, one could search for additional parameters that are easier to certify than tree-length: any invariant that is sandwiched between two bounded functions of $tl$ will automatically join the class.","The polynomial-time computability of $bnc$ and $mcw$, though with worse constants than the 3-approximation via layering partitions, suggests these parameters could serve as certificates or upper-bound witnesses in algorithms where tree-length itself is NP-hard to compute.","The open question whether $br(G) = tb(G)$ could be tested by exhaustively computing both parameters on small graphs; a positive answer would make the bramble-piercing radius an exact, not just coarse, dual of tree-breadth.","The cycle bridging and non-locally geodesic constants are defined by local checks; one might try to turn them into polynomial-time certificates of bounded tree-length, though the paper does not claim an algorithm for them."],"forward_implications":["Because a layering partition is computed in linear time, its cluster-diameter gives a fast constant-factor approximation to tree-length and to every parameter on the list.","Any structural or algorithmic result proved for bounded tree-length now applies verbatim to graphs with bounded bramble-interception radius, bounded Helly-family interception radius, bounded additive tree distortion, or bounded cycle bridging constant.","The embedding result says that bounded tree-length is equivalent to embedding the graph's own vertices into an unweighted tree with small additive distortion and no Steiner points, the strongest form of tree approximation on the list.","The bramble and Helly characterizations give a min-max flavor to tree-breadth: a small-radius disk pierces every pairwise-touching connected family exactly when the graph has a tree-decomposition of small breadth.","The cycle bridging constant provides a purely local cycle condition that certifies bounded tree-length, generalizing the chordal graph property that every vertex in a cycle has two neighbors that are adjacent."],"supporting_citations":[{"why":"Supplies the fundamental sandwich $\\Delta_s(G)/3 \\leq tl(G) \\leq \\Delta_s(G)+1$, the bridge used throughout the paper.","marker":"[27]"},{"why":"Gives the start-vertex independence bound $\\Delta_q(G) \\leq 3\\Delta_s(G)$, letting the paper pass from one layering partition to the worst-case cluster-diameter.","marker":"[35]"},{"why":"Provides the canonical tree and the inequality chain tying cluster-diameter to non-contractive tree embedding, used in the $adt$ results.","marker":"[21]"},{"why":"Supplies the tree-breadth sandwich $\\rho_s(G)/3 \\leq tb(G) \\leq \\rho_s(G)+1$ and the balanced-disk separator technique used for McCarty-width.","marker":"[32]"},{"why":"Records the cluster-radius/tree-breadth and tree-distortion bounds used in the preliminary inequalities.","marker":"[1]"},{"why":"Establishes the earlier coarse equivalences for $ad$, $bnc$, $mcw$, and geodesic loaded cycles whose proofs this paper simplifies and extends.","marker":"[9]"},{"why":"Introduces $K$-fat $K_3$-minors and their equivalence with bounded bottleneck constant, the basis for the $mf$ parameter.","marker":"[44]"},{"why":"Proves that every bramble is intersected by a bag of every tree-decomposition, which gives $br(G) \\leq tb(G)$.","marker":"[58]"},{"why":"Provides the balanced clique separator for chordal graphs used to prove $mcw_k(G) \\leq tb(G)$.","marker":"[45]"}],"fun_headline_variants":["18 graph parameters fold into one tree-length scale","Tree-length: the single scale for 18 graph invariants","New proofs: brambles, Helly families, and cycles match tree-length","Bridging cycles to tree-length: new equivalence proof","Tree-length governs 18 parameters, from brambles to cycle bridges"],"cache_read_input_tokens":34048,"weakest_assumption_plain":"The chain of equivalences rests on previously published inequalities, most crucially that every graph satisfies $\\Delta_s(G)/3 \\leq tl(G) \\leq \\Delta_s(G)+1$ for the cluster-diameter of any layering partition, and if those quoted bounds failed, all the new constants would shift, even though the qualitative bounded-versus-bounded picture could survive.","fun_headline_variants_meta":{"raw":{"variants":["18 graph parameters fold into one tree-length scale","Tree-length: the single scale for 18 graph invariants","New proofs: brambles, Helly families, and cycles match tree-length","Bridging cycles to tree-length: new equivalence proof","Tree-length governs 18 parameters, from brambles to cycle bridges"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000897,"raw_usage":{"total_tokens":3942,"prompt_tokens":1101,"completion_tokens":2841,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":717,"completion_tokens_details":{"reasoning_tokens":2753}},"tokens_in":717,"tokens_out":2841,"duration_ms":20570,"temperature":1.0,"reasoning_tokens":2753,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T17:13:04.815411+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a chordal graph (tree-length 1) with unbounded clique size and compute the bramble interception radius $br(G)$: the theorem predicts $br(G) \\leq 1$, so any chordal graph whose brambles require a disk of radius 2 or more would refute the claimed coarse equivalence between $br$ and tree-breadth.","supporting_citations":[{"cited_title":"Dourisboure, C","cited_arxiv_id":null,"evidence_quote":"Supplies the fundamental sandwich $\\Delta_s(G)/3 \\leq tl(G) \\leq \\Delta_s(G)+1$, the bridge used throughout the paper."},{"cited_title":"Dragan, A","cited_arxiv_id":null,"evidence_quote":"Gives the start-vertex independence bound $\\Delta_q(G) \\leq 3\\Delta_s(G)$, letting the paper pass from one layering partition to the worst-case cluster-diameter."},{"cited_title":"Chepoi, F.F","cited_arxiv_id":null,"evidence_quote":"Provides the canonical tree and the inequality chain tying cluster-diameter to non-contractive tree embedding, used in the $adt$ results."},{"cited_title":"Dragan, E","cited_arxiv_id":null,"evidence_quote":"Supplies the tree-breadth sandwich $\\rho_s(G)/3 \\leq tb(G) \\leq \\rho_s(G)+1$ and the balanced-disk separator technique used for McCarty-width."},{"cited_title":"Abu-Ata, F.F","cited_arxiv_id":null,"evidence_quote":"Records the cluster-radius/tree-breadth and tree-distortion bounds used in the preliminary inequalities."},{"cited_title":"Gilbert, D.J","cited_arxiv_id":null,"evidence_quote":"Provides the balanced clique separator for chordal graphs used to prove $mcw_k(G) \\leq tb(G)$."}],"review_version":1}