An approximate cactus-decomposition for vertex-connectivity

arXiv:2611.01772 · math.CO, cs.DM · Submitted 2026-11-01 · Read on arXiv

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

Related papers