Zhongtian He, Princeton University

Abstract

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. 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.

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. We also give the first deterministic near-linear time algorithm for constructing the cactus representation of all global minimum cuts.

This talk is based on two papers by Zhongtian He, Shang-En Huang, and Thatchaphol Saranurak in SODA’24.

See: https://theory.cs.rutgers.edu/theory_seminar