APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time

We design an$n^{2+o(1)}$-time algorithm that constructs a cut-equivalent (Gomory-Hu) tree of a simple graph on$n$nodes. This bound is almost-optimal in terms of$n$, and it improves on the recent$\tilde{O}(n^{2.5})$bound by the authors (STOC 2021), which was the first to break the cubic barrier. Consequently, the All-Pairs Maximum-Flow (APMF) problem has time complexity$n^{2+o(1)}$, and for the first time in history, this problem can be solved faster than All-Pairs Shortest Paths (APSP). We further observe that an almost-linear time algorithm (in terms of the number of edges$m$) is not possible without first obtaining a subcubic algorithm for multigraphs. Finally, we derandomize our algorithm, obtaining the first subcubic deterministic algorithm for Gomory-Hu Tree in simple graphs, showing that randomness is not necessary for beating the$n-1$times max-flow bound from 1961. The upper bound is$\tilde{O}(n^{2\frac{2}{3}})$and it would improve to$n^{2+o(1)}\ \mathbf{i}\mathbf{f}$there is a deterministic single-pair maximum-flow algorithm that is almost-linear. The key novelty is in using a “dynamic pivot” technique instead of the randomized pivot selection that was central in recent works.