Near-Linear Time Approximations for Cut Problems via Fair Cuts

We introduce the notion of 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 α ≥ 1, an α-fair (s, t)-cut is an (s, t)-cut such that there exists an (s, t)-flow that uses 1/α fraction of the capacity of every edge in the cut. (So, any α-fair cut is also an α-approximate mincut, but not vice-versa.) We give an algorithm for (1 + ε)-fair (s, t)-cut in Õ(m)-time, thereby matching the best runtime for (1 + ε)-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 + ε)-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+ε)-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]. * The full version of the paper can be accessed at https://arxiv.org/abs/2203.00751