Gomory-Hu Tree in Subcubic Time

In 1961, Gomory and Hu showed that the max-flow values of all $n\choose 2$ pairs of vertices in an undirected graph can be computed using only $n-1$ calls to any max-flow algorithm, and succinctly represented them in a tree (called the Gomory-Hu tree later). Even assuming a linear-time max-flow algorithm, this yields a running time of $O(mn)$ for this problem; with current max-flow algorithms, the running time is $\tilde{O}(mn + n^{5/2})$. We break this 60-year old barrier by giving an $\tilde{O}(n^{2})$-time algorithm for the Gomory-Hu tree problem, already with current max-flow algorithms. For unweighted graphs, our techniques show equivalence (up to poly-logarithmic factors in running time) between Gomory-Hu tree (i.e., all-pairs max-flow values) and a single-pair max-flow.