The speaker is Ohad
Trabelsi (Weizmann).
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 an O(n^2) · 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)·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
was shown 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 state-of-the-art as
long as m = O(n^(5/3−ε)). Finally, we explain the lack of lower bounds by
proving a non-reducibility result. This result is based on a new quasi-linear
time \tO(m) non-deterministic algorithm for constructing a cut-equivalent tree
and may be of independent interest.
