Volume 17 (2021) Article 5 pp. 1-27

New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs

by Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi

Received: December 19, 2019
Revised: August 29, 2020
Published: September 20, 2021

$\newcommand{\ensuremath}[1]{#1} \newcommand{\ProblemName}[1]{\textsf{#1}} \newcommand{\MF}{\ProblemName{Max-Flow}} \newcommand{\APMF}{\ProblemName{All-Pairs Max-Flow}} \newcommand\tO{\ensuremath{\widetilde O}}$

We investigate the time-complexity of the $\APMF$ problem: Given a graph with $n$ nodes and $m$ edges, compute for all pairs of nodes the maximum-flow value between them. If $\MF$ (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 $\MF$ 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 $\APMF$ 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 $\MF$ 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).

DOI: 10.4086/toc.2021.v017a005

© 2021 Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi
Licensed under a Creative Commons Attribution License (CC-BY)