An approximate cactus-decomposition for vertex-connectivity
math.CO, cs.DM
Submitted: 2026-11-01
Updated: 2026-11-01
Code: https://github.com/j-carmesin/j-carmesin.github.io
License: http://creativecommons.org/licenses/by/4.0/
The gist: The classical cactus theorem of Dinitz, Karzanov and Lomonosov from 1976 states that the minimum edge-cuts of a connected graph are displayed by a cactus.
Abstract
The classical cactus theorem of Dinitz, Karzanov and Lomonosov from 1976 states that the minimum edge-cuts of a connected graph are displayed by a cactus. For vertex-separations, Tutte's theorem gives an exact cactus-decomposition for connectivity 2, but exact cactus-decompositions fail for higher connectivity. Extending earlier approximate cactus-decomposition results for connectivities 3 and 4 by Carmesin and Kurkofka [FOCS 2023] and Kurkofka and Planken [SODA 2026] to all connectivities, we prove that for every k in N there is a constant d=d(k) such that every k-connected graph G admits a cactus-decomposition displaying k-separations such that every k-separation of G has edit-distance at most d to a displayed separation. Our proof develops tools that may be useful beyond this result. The first is a three-dimensional version of the classical corner-diagram method, which we use to show that triples of crossing k-separations have a controlled two-dimensional behaviour. The second is a covering-space approach for studying local crossing patterns from a global perspective. Third, we advance the theory of flowers, which originated in matroid theory.
Sources
- Locally chordal graphs
- Decomposition of (infinite) digraphs along directed 1-separations
- How to apply tree decomposition ideas in large networks?
- Canonical graph decompositions via coverings
- Improved Approximations for Relative Survivable Network Design
- Tangles and the Mona Lisa
- A generalization of the Grid Theorem
- Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles)
- Canonical tree-decompositions of chordal graphs
- Canonical graph decompositions via local separations
- A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation
- A characterisation of all vertex-transitive finite graphs of connectivity < 5
- Connectivity augmentation is fixed-parameter tractable
- On $k$-connectivity oracles in $k$-connected graphs
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality