Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts

of O(n) size that exactly captures all global minimum cuts of the graph. It is a central com-
binatorial 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 con-
structions 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 very influential isolating min-
cut 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 many future applications.