Pith. sign in

REVIEW 8 minor 22 references

Every graph splits along coarse cut-vertices into coarse 2-connected pieces

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

Every graph admits a tree decomposition with small-diameter adhesion sets where same-bag vertices cannot be separated by small, distant vertex sets.

T0 review reviewed 2026-07-09 challenge →

load-bearing objection Clean, correct coarse analogue of the block-cut tree theorem using BFS-layering; the proof is short and modular, with a sensible dual formulation. The constants are loose but that is expected in this area.

arxiv 2607.07111 v1 pith:GOCCPBYQ submitted 2026-07-08 math.CO cs.DM

A coarse block-cut tree theorem

J\'ulia Balig\'acs , V\'aclav Bla\v{z}ej , Jadwiga Czy\.zewska , Micha{\l} Pilipczuk , Evangelos Protopapas This is my paper
classification math.CO cs.DM
keywords coarse graph theorytree decompositionblock-cut treeBFS layeringweak diametercoarse Menger theorem2-connected components
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

The classic block-cut tree theorem says every graph decomposes along its cut-vertices into 2-connected components, arranged in a tree. This paper proves a coarse analogue: for every graph and every positive integer d, one can build a tree decomposition whose adhesion sets (the overlaps between neighboring bags) have weak diameter at most 3d+2, and such that no two vertices sharing a bag can be separated by a small-diameter set that stays far from both. The construction repurposes a BFS-layering technique: partition vertices into distance layers from a root, then split each layer into blocks according to connectivity in all deeper layers. Blocks of bounded diameter act as coarse cut-vertices; wide blocks become parts of coarse 2-connected components. The separator-free guarantee for same-bag vertices follows because any candidate separator of diameter at most d either sits too shallow in the layering to block paths (Lemma 2) or must cross a wide block that is too large to be fully covered (Lemma 3). A dual formulation, obtained via a coarse Menger theorem for two paths, rephrases the non-separability condition as the existence of two well-separated paths connecting the vicinities of any two far-apart same-bag vertices.

Core claim

The central mechanism is the BFS-layering tree of blocks. Given a root r, vertices are partitioned into layers by distance from r, and within each layer, vertices are grouped into blocks by their connectivity in the subgraph induced by that layer and all deeper ones. This block structure forms a tree. The decomposition then contracts maximal subtrees of wide (large-diameter) blocks into single bags and keeps narrow (bounded-diameter) blocks as adhesion sets. The key structural fact is that on any path through the decomposition tree between two blocks belonging to the same bag, all intermediate blocks are wide, which forces any small-diameter separator to miss at least one of them, leaving a逃

What carries the argument

BFS-layering into blocks (Berger-Seymour construction), where blocks are equivalence classes of same-layer vertices connected through deeper layers; the block tree T_L is always a tree; d-compact blocks (diameter at most d) serve as adhesion sets while connected components of d-wide blocks form bags; Lemma 2 handles shallow separators via shortest-path arguments, Lemma 3 handles deep separators by exploiting the width of an intermediate block on the BFS-tree path.

Load-bearing premise

The separator-free guarantee for vertices in the same bag hinges on the fact that any block lying internally on a path between two same-bag blocks in the decomposition tree must be wide (have diameter exceeding 3d+2). This follows from the construction, but if the layering or block definitions were modified even slightly, this property could fail and the entire non-separation argument would collapse.

What would settle it

A graph G and integer d for which, in every possible tree decomposition with adhesion sets of weak diameter at most 3d+2, there exist two vertices u, v in some common bag and a set S with diam(S) at most d, dist(S, {u,v}) > d+1, that separates u from v in G. Such an example would show the decomposition cannot simultaneously achieve bounded adhesion and the non-separation property.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Provides a constructive, polynomial-time decomposition that could serve as a preprocessing step for algorithms on graphs with quasi-isometric tree-like structure.
  • The dual formulation connects the decomposition to the existence of well-separated path pairs, bridging structural decompositions with coarse Menger-type flow statements.
  • Suggests that other classic structural decomposition theorems (e.g., along 3-connected components or clique-sums) may admit coarse analogues via similar layering-and-blocking techniques.
  • The constant 3d+2 on adhesion-set diameter and the constant 129c in the dual formulation leave room for tightening, which could improve quantitative guarantees in downstream applications.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the coarse block-cut decomposition could be made canonical (independent of root choice up to bounded perturbation), it would provide a quasi-isometry invariant of graphs analogous to the classical block-cut tree being a graph invariant.
  • The technique of using BFS-layering blocks as a skeleton for coarse decompositions might extend to directed graphs or to graphs with weighted metrics, though the tree structure of the block graph relies on undirected connectivity properties that may not transfer directly.
  • The gap between the 3d+2 adhesion bound and the d separator bound suggests a possible lower-bound construction showing this linear blow-up is necessary, which would clarify whether the constants are artifacts of the proof or intrinsic to the problem.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 8 minor

Summary. This paper proves a coarse analogue of the classical block-cut tree theorem. The main result (Theorem 1) states that for every connected graph G and positive integer d, there exists a tree-decomposition whose adhesion sets have weak diameter at most 3d+2, and such that no two vertices u, v in a common bag can be separated by a set S of weak diameter at most d with dist(S, {u,v}) > d+1. The construction builds on the BFS-layering technique of Berger and Seymour [6], partitioning each layer into blocks (equivalence classes of connectivity in the tail of the layering), classifying blocks as d'-compact or d'-wide (d' = 3d+2), and forming a tree-decomposition where compact blocks serve as adhesion sets and wide blocks are grouped into component bags. The separator-free property is verified through two lemmas (Lemmas 2 and 3) handling cases based on the maximum layer reached by the separator. A dual formulation (Corollary 1) is derived using the Coarse Menger's Theorem for two paths (Theorem 2, from [5, 12]).

Significance. This is a clean and well-motivated contribution to coarse graph theory, adding a positive example to the growing list of coarse analogues of classical structural results. The block-cut tree is one of the most fundamental decomposition tools in graph theory, and its coarse counterpart is a natural and important object. The proof technique is elegant and modular: the construction of the decomposition tree (Lemma 1) is straightforward, and the separator-free property (Theorem 1) reduces to two well-separated cases (Lemmas 2 and 3). The dual formulation (Corollary 1) via coarse Menger for two paths is a nice addition that makes the 'coarse 2-connectivity' condition more concrete. The algorithmic aspect (polynomial-time computability, Observation 3) is also a plus. The authors note that a similar result was independently obtained by Albrechtsen and Georgakopoulos [4], which is appropriately disclosed.

minor comments (8)
  1. Abstract: The abstract states 'whose distance from u and v is more than d', while Theorem 1 and the body use the condition dist_G(S, {u,v}) > d+1. This minor discrepancy should be reconciled for precision.
  2. Lemma 3: The statement uses 'B' (the block containing v) in the hypothesis but the proof operates on B' and v*. The role of B in the lemma statement is unclear since it is not used in the conclusion or proof beyond context. Consider clarifying whether B is needed in the statement or whether the lemma could be stated purely in terms of B_u and B'.
  3. Proof of Theorem 1: The notation 'bB' for the least common ancestor of B_u and B_v is slightly unusual; consider using a more standard notation such as B_hat or B_lca.
  4. Lemma 4, second part: The argument that 'no vertex in N^{ell-(2cd+1)}[u] and N^{ell-(2cd+1)}[v] belongs to F' uses the fact that dist(u,z) >= ell and dist(v,z) >= ell for z in P intersect F. This is correct but the reasoning could be made slightly more explicit, as it relies on the shortest-path property of P and the disjointness of N^ell[u] and N^ell[v].
  5. Corollary 1: The constant floor(d/258) arises from d/(2c) with c=129. It would help the reader to briefly note this derivation explicitly, e.g., 'where 258 = 2c = 2 * 129'.
  6. Section 3, definition of T^d_L: The node types are described clearly, but a small illustrative figure showing the transformation from T_L to T^d_L would significantly aid readability.
  7. Introduction: The phrase 'The coarse analogue of the Kuratowski-Wagner Theorem remains tantalizingly open [12]' could benefit from a brief parenthetical explaining what the coarse analogue would assert, for readers not deeply familiar with the program.
  8. References: Several arXiv preprints are cited with 2026 dates (e.g., [7], [8], [9], [15], [16]–[21]). These should be verified for accuracy and updated with final publication details if available.

Circularity Check

0 steps flagged

No circularity found; derivation is self-contained with external support

full rationale

The proof of Theorem 1 constructs a tree-decomposition from a BFS-layering and verifies both conditions through direct structural arguments (Lemmas 1–3). The key step — that block B' must be d'-wide because it is internal on the B_u–B_v path in T_L and by construction internal blocks on such paths cannot be d'-compact — is a genuine structural consequence, not a definitional equivalence. The dual formulation (Corollary 1) relies on Theorem 2 (coarse Menger for two paths) from [5, 12], both of which are external works with no author overlap with the current paper. The self-citation [7] (three of five current authors) appears only in the introduction as a related result and is not load-bearing for any proof step. No parameter is fitted and then 'predicted'; d is an input parameter throughout. No step reduces to its own inputs by construction or self-citation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper introduces no free parameters, no ad hoc axioms, and no invented entities. The constant 3d+2 emerges from the proof structure (d for separator diameter, d+1 for distance, and a factor of 3 from the width condition). The constant c=129 is imported from cited literature [5].

axioms (2)
  • standard math Coarse Menger's Theorem for two paths (Theorem 2 from [5, 12])
    Used in Section 4 to derive the dual formulation (Corollary 1). States that if no two S-T paths are d-far, a single vertex is within 129d of all S-T paths.
  • standard math BFS-layering tree structure (Observation 1, from [6])
    The construction of the tree T_L from BFS layers and their blocks is a standard graph-theoretic fact, used as the structural foundation for the decomposition.

reviewed 2026-07-09 · how reviews work

0 comments
Cite this review

Pith. "Pith review of A coarse block-cut tree theorem." pith.science (2026). https://pith.science/paper/GOCCPBYQ

@misc{pith2026260707111,
  author       = {Pith},
  title        = {Pith review of: A coarse block-cut tree theorem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GOCCPBYQ}},
  note         = {Machine review of arXiv:2607.07111}
}
Share X Bluesky LinkedIn Reddit HN
abstract

We prove a coarse analogue of the classic fact that every graph can be decomposed along its cut-vertices into $2$-connected components. Precisely, we prove that for every graph $G$ and a positive integer $d$, $G$ admits a tree decomposition whose adhesion sets have weak diameter at most $3d+2$ so that no two vertices $u,v$ lying in the same bag can be separated by a set of weak diameter at most $d$ whose distance from $u$ and $v$ is more than $d$. By the Coarse Menger's Theorem for two paths, this condition admits also a dual formulation, phrased in terms of the existence of two paths that are far from each other and connect the vicinity of $u$ with the vicinity of $v$.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages · 11 internal anchors

  1. [1]

    J. Ahn, J. P. Gollin, T. Huynh, and O. Kwon. A coarse Erd˝os-P´osa theorem. In36th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, pages 3363–3381. SIAM, 2025. 8

    work page 2025

  2. [2]

    Albrechtsen, M

    S. Albrechtsen, M. Bonamy, R. Bourneuf, and J. Davies. Manuscript in preparation

    work page

  3. [3]

    Albrechtsen and J

    S. Albrechtsen and J. Davies. Counterexample to the conjectured coarse grid theorem.ArXiv preprint, abs/2508.15342, 2025

    work page arXiv 2025

  4. [4]

    Albrechtsen and A

    S. Albrechtsen and A. Georgakopoulos. A coarse block-cutvertex tree-decomposition. Manuscript

    work page

  5. [5]

    Albrechtsen, T

    S. Albrechtsen, T. Huynh, R. W. Jacobs, P. Knappe, and P. Wollan. A Menger-type theorem for two induced paths.SIAM Journal on Discrete Mathematics, 38(2):1438–1450, 2024

    work page 2024

  6. [6]

    Berger and P

    E. Berger and P. Seymour. Bounded-diameter tree-decompositions.Combinatorica, 44(3):659–674, 2024

    work page 2024

  7. [7]

    A coarse Menger's Theorem for planar and bounded genus graphs

    V. Bla ˇzej, M. Pilipczuk, and E. Protopapas. A coarse Menger’s Theorem for planar and bounded genus graphs.ArXiv preprint, abs/2605.11112, 2026. Accepted to FOCS 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  8. [8]

    Coarse Balanced Separators in Fat-Minor-Free Graphs

    E. Bonnet, H. Le, M. Pilipczuk, and M. Pilipczuk. Coarse balanced separators in fat-minor-free graphs. ArXiv preprint, abs/2604.11318, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  9. [9]

    Distel, U

    M. Distel, U. Giocanti, J. Hodor, C. Legrand-Duchesne, and P. Micek. A coarse Gallai theorem.ArXiv preprint, abs/2601.18439, 2026

    work page arXiv 2026

  10. [10]

    Erd\H{o}s--P\'{o}sa property of cycles that are far apart

    V. Dujmovi ´c, G. Joret, P. Micek, and P. Morin. Erd˝os-P´osa property of cycles that are far apart.ArXiv preprint, abs/2412.13893, 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  11. [11]

    On Induced Versions of Menger's Theorem on Sparse Graphs

    P. Gartland, T. Korhonen, and D. Lokshtanov. On induced versions of Menger’s theorem on sparse graphs.ArXiv preprint, abs/2309.08169, 2023

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  12. [12]

    Georgakopoulos and P

    A. Georgakopoulos and P. Papasoglu. Graph minors and metric spaces.Combinatorica, 45(3):Paper No. 33, 29, 2025

    work page 2025

  13. [13]

    Hendrey, S

    K. Hendrey, S. Norin, R. Steiner, and J. Turcotte. On an induced version of Menger’s theorem.Elec- tronic Journal of Combinatorics, 31(4), 2024

    work page 2024

  14. [14]

    Graphs that are quasi-isometric to graphs with bounded treewidth

    R. Hickingbotham. Graphs that are quasi-isometric to graphs with bounded treewidth.ArXiv preprint, abs/2501.10840, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  15. [15]

    C.-H. Liu. Coarse Menger property of quasi-minor excluded graphs and length spaces.ArXiv preprint, abs/2605.10068, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  16. [16]

    Asymptotic structure. I. Coarse tree-width

    T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure. I. Coarse tree-width.ArXiv preprint, abs/2501.09839, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  17. [17]

    Nguyen, A

    T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure. II. Path-width and additive quasi-isometry. ArXiv preprint, abs/2509.09031, 2025

    work page arXiv 2025

  18. [18]

    Asymptotic structure. III. Excluding a fat tree

    T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure. III. Excluding a fat tree.ArXiv preprint, abs/2509.09035, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  19. [19]

    Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture

    T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture.ArXiv preprint, abs/2508.14332, 2025. 9

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  20. [20]

    Asymptotic structure. V. The coarse Menger conjecture in bounded path-width

    T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure. V. The coarse Menger conjecture in bounded path-width.ArXiv preprint, abs/2509.08762, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  21. [21]

    Asymptotic structure. VI. Distant paths across a disc

    T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure. VI. Distant paths across a disc.ArXiv preprint, abs/2509.07174, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  22. [22]

    Nguyen, A

    T. Nguyen, A. Scott, and P. Seymour. A counterexample to the coarse Menger conjecture.Journal of Combinatorial Theory, Series B, 173:68–82, 2025. 10

    work page 2025

This paper was first reviewed by glm-5.2 on July 9, 2026.