Theory of Computing
-------------------
Title     : New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
Authors   : Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi
Volume    : 17
Number    : 5
Pages     : 1-27
URL       : https://theoryofcomputing.org/articles/v017a005

Abstract
--------

We investigate the time-complexity of the All-Pairs-Max-Flow problem:
Given a graph with $n$ nodes and $m$ edges, compute for all pairs of
nodes the maximum-flow value between them. If Max-Flow (the version
with a given source-sink pair $s,t$) can be solved in time $T(m)$,
then $O(n^2)\cdot T(m)$ is a trivial upper bound. But can we do better?

For directed graphs, recent results in fine-grained complexity suggest
that this time bound is essentially optimal. In contrast, for
undirected graphs with edge capacities, a seminal algorithm of Gomory
and Hu (1961) runs in much faster time, $O(n)\cdot T(m)$. Under the
plausible assumption that Max-Flow can be solved in near-linear time
$m^{1+o(1)}$, this half-century old algorithm yields an $nm^{1+o(1)}$
bound. Several other algorithms have been designed through the years,
including ${\tO}(mn)$ time for unit-capacity edges (unconditionally),
but none of them break the $O(mn)$ barrier. Meanwhile, no super-linear
lower bound is known for undirected graphs.

We design the first hardness reductions for All-Pairs-Max-Flow in
undirected graphs, giving an essentially optimal lower bound for the
_node-capacities_ setting. For edge capacities, our efforts to prove
similar lower bounds have failed, but we have discovered a surprising
new algorithm that breaks the $O(mn)$ barrier for graphs with unit-
capacity edges! Assuming $T(m)=m^{1+o(1)}$, our algorithm runs in time
$m^{3/2 +o(1)}$ and outputs a cut-equivalent tree (similarly to the
Gomory--Hu algorithm). Even with current Max-Flow algorithms we improve
the state of the art as long as $m=O(n^{5/3-\varepsilon})$. Finally,
we explain the lack of lower bounds by proving a _non-reducibility_
result. This result is based on a new near-linear time $\tO(m)$
_nondeterministic_ algorithm for constructing a cut-equivalent tree
and may be of independent interest.

------------------

A conference version of this paper appeared in the
Proceedings of the 31st ACM-SIAM Symposium on Discrete
Algorithms (SODA'20)</a>.