Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts

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. In a long line of work on fast constructions of cactus and its generalizations, a near-linear time construction of cactus was shown by Karger and Panigrahi [SODA'09]. Unfortunately, their technique based on tree packing inherently does not generalize. The state-of-the-art algorithms for Steiner cactus and hypercactus are still slower than linear time by a factor of Ω(|T |) [Dinitz and Vainshtein STOC'94] and Ω(n) [Chekuri and Xu SODA'17], respectively.

We show how to construct both Steiner cactus and hypercactus using polylogarithmic calls to max flow, which gives the first almost-linear time algorithms of both problems. The constructions immediately imply almost-linear-time connectivity augmentation algorithms in the Steiner and hypergraph settings, as well as speed up the incremental algorithm for maintaining minimum cuts in hypergraphs by a factor of n.

The key technique behind our result is a novel variant of the influential isolating mincut technique [Li and Panigrahi FOCS'20, Abboud et al. STOC'21] which we called maximal isolating mincuts. This technique makes the isolating mincuts to be "more balanced" which, we believe, will likely be useful in future applications.