Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Near-Linear Time Approximations for Cut Problems via Fair Cuts


Nanongkai,  Danupon       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 972KB

Supplementary Material (public)
There is no public supplementary material available

Li, J., Nanongkai, D., Panigrahi, D., & Saranurak, T. (2022). Near-Linear Time Approximations for Cut Problems via Fair Cuts. Retrieved from https://arxiv.org/abs/2203.00751.

Cite as: https://hdl.handle.net/21.11116/0000-000E-6DA9-A
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
- 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].