arXiv:2611.01772 · v1

An approximate cactus-decomposition for vertex-connectivity

首次提交 2026-11-01 18:23

版本更新 2026-11-01 18:23

雷达观测 2026-11-04 23:43

摘要

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\mathbb{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.