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

In 1961, Gomory and Hu showed that the All-Pairs Max-Flow problem of computing the max-flow between all n 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 = Θ(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 Õ(n 2 )-time algorithm on general, weighted graphs. Combined with a popular complexity assumption, we establish a counter-intuitive separation: all-pairs max-flows are strictly easier to compute than all-pairs shortest-paths.

Our algorithm produces a cut-equivalent tree, known as the Gomory-Hu tree, from which the max-flow value for any pair can be retrieved in near-constant time. For unweighted graphs, we refine our techniques further to produce a Gomory-Hu tree in the time of a poly-logarithmic number of calls to any max-flow algorithm. This shows an equivalence between the all-pairs and single-pair max-flow problems, and is optimal up to poly-logarithmic factors. Using the recently announced m 1+o(1) -time max-flow algorithm (Chen et al., March 2022), our Gomory-Hu tree algorithm for unweighted graphs also runs in m 1+o(1) -time.

The first version of this paper (arXiv:2111.04958) titled "Gomory-Hu Tree in Subcubic Time" (Nov. 9, 2021) broke the cubic barrier but only claimed a time bound of Õ(n 2.875 ). The second version (Nov. 30, 2021) optimized one of the ingredients (Section 2) and gave the Õ(n 2 ) time bound. The latter optimization was discovered independently by Zhang [Zha21].