Near-Linear Time Approximations for Cut Problems via Fair Cuts

Download PDF

We introduce the notion of {\em fair cuts} as an approach to leverage approximate (s,t)-mincut (equivalently (s,t)-maxflow) algorithms in undirected graphs to obtain near-linear time approximation algorithms for several cut problems. Informally, for any \alpha\geq 1, an \alpha-fair (s,t)-cut is an (s,t)-cut such that there exists an (s,t)-flow that uses 1/\alpha fraction of the capacity of \emph{every} edge in the cut. (So, any \alpha-fair cut is also an \alpha-approximate mincut, but not vice-versa.) We give an algorithm for (1+\epsilon)-fair (s,t)-cut in \tilde{O}(m)-time, thereby matching the best runtime for (1+\epsilon)-approximate (s,t)-mincut [Peng, SODA '16]. We then demonstrate the power of this approach by showing that this result almost immediately leads to several applications:
- the first nearly-linear time (1+\epsilon)-approximation algorithm that computes all-pairs maxflow values (by constructing an approximate Gomory-Hu tree). Prior to our work, such a result was not known even for the special case of Steiner mincut [Dinitz and Vainstein, STOC '94; Cole and Hariharan, STOC '03];
- the first almost-linear-work subpolynomial-depth parallel algorithms for computing (1+\epsilon)-approximations for all-pairs maxflow values (again via an approximate Gomory-Hu tree) in unweighted graphs;
- the first near-linear time expander decomposition algorithm that works even when the expansion parameter is polynomially small; this subsumes previous incomparable algorithms [Nanongkai and Saranurak, FOCS '17; Wulff-Nilsen, FOCS '17; Saranurak and Wang, SODA '19].