# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Near-Linear Time Approximations for Cut Problems via Fair Cuts

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2203.00751.pdf

(Preprint), 972KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

##### Abstract

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

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