Gomory-Hu Trees in Quadratic Time

Understand

Gomory-Hu tree [Gomory and Hu, 1961] is a succinct representation of pairwise minimum cuts in an undirected graph.

• When the input graph has general edge weights, classic algorithms need at least cubic running time to compute a Gomory-Hu tree.
• Very recently, the authors of [AKL+, arXiv v1, 2021] have improved the running time to $\tilde{O}(n^{2.875})$ which breaks the cubic barrier for the first time.
• In this paper, we refine their approach and improve the running time to $\tilde{O}(n^2)$.