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

},\n}\n"