{"id":"arxiv/2611.01772","url":"https://arxiv.org/abs/2611.01772","tags":["math.CO","cs.DM"],"score":0,"title":"An approximate cactus-decomposition for vertex-connectivity","domain":"math.CO","source":"arxiv","authors":["Romain Bourneuf","Johannes Carmesin","Jan Kurkofka","Tim Planken"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-01","reactions":{}}