Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time

Understand

In 1961, Gomory and Hu showed that the All-Pairs Max-Flow problem of computing the max-flow between all $n\choose 2$ pairs of vertices in an undirected graph can be solved using only $n-1$ calls to any (single-pair) max-flow algorithm.

• Even assuming a linear-time max-flow algorithm, this yields a running time of $O(mn)$, which is $O(n^3)$ when $m = \Theta(n^2)$.
• While subsequent work has improved this bound for various special graph classes, no subcubic-time algorithm has been obtained in the last 60 years for general graphs.
• We break this longstanding barrier by giving an $\tilde{O}(n^{2})$-time algorithm on general, weighted graphs.