Skip to main content

Near-Linear Time Approximations for Cut Problems via Fair Cuts

Publication ,  Conference
Li, J; Nanongkai, D; Panigrahi, D; Saranurak, T
Published in: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
January 1, 2023

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

Duke Scholars

Published In

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Publication Date

January 1, 2023

Volume

2023-January

Start / End Page

240 / 275
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Li, J., Nanongkai, D., Panigrahi, D., & Saranurak, T. (2023). Near-Linear Time Approximations for Cut Problems via Fair Cuts. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 2023-January, pp. 240–275).
Li, J., D. Nanongkai, D. Panigrahi, and T. Saranurak. “Near-Linear Time Approximations for Cut Problems via Fair Cuts.” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2023-January:240–75, 2023.
Li J, Nanongkai D, Panigrahi D, Saranurak T. Near-Linear Time Approximations for Cut Problems via Fair Cuts. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. 2023. p. 240–75.
Li, J., et al. “Near-Linear Time Approximations for Cut Problems via Fair Cuts.” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2023-January, 2023, pp. 240–75.
Li J, Nanongkai D, Panigrahi D, Saranurak T. Near-Linear Time Approximations for Cut Problems via Fair Cuts. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. 2023. p. 240–275.

Published In

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Publication Date

January 1, 2023

Volume

2023-January

Start / End Page

240 / 275