Structure
Cycles + bridges glued together. Block-cut tree gives natural decomposition.
Advertisement
Polynomial problems
Hamiltonian path, longest path, min vertex cover — all polynomial on cactus. Trees + cycles are individually tractable.
Advertisement
Applications in modeling
All-pairs min cut structure of a graph = cactus of min cuts. Represents cut structure compactly.
Min cut cactus
Dinits-Karzanov-Lomonosov: any graph's min cuts form a cactus. O(V·E + V² log V) to construct.