Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak · Society for Industrial and Applied Mathematics eBooks · 2024
A cactus representation of a graph, introduced by Dinitz et al. in 1976, is an edge sparsifier of O(n) size that exactly captures all global minimum cuts of the graph. It is a central combinatorial object that has been a key ingredient in almost all algorithms for the connectivity augmentation problems and for maintaining minimum cuts under edge insertions (e.g. [Naor et al. SICOMP’97], [Cen et al. SODA’22], [Henzinger ICALP’95]). This sparsifier was generalized to Steiner cactus for a vertex set T, which can be seen as a vertex sparsifier of O(|T|) size that captures all partitions of T corresponding to a T-Steiner minimum cut, and also hypercactus, an analogous concept in hypergraphs. These generalizations further extend the applications of cactus to the Steiner and hypergraph settings.