Approximate Gomory–Hu Tree is Faster than \(\boldsymbol{n}\,\boldsymbol{-\, 1}\) Maximum Flows
Jason Li, Debmalya Panigrahi · SIAM Journal on Computing · 2024
Abstract. The Gomory–Hu tree or cut tree [R. E. Gomory and T. C. Hu, J. Soc. Indust. Appl. Math., 9 (1961), pp. 551–570] is a classic data structure for reporting [Formula: see text]-mincuts (and by duality, the values of [Formula: see text]-maxflows) for all-pairs of vertices [Formula: see text] and [Formula: see text] in an undirected graph. Gomory and Hu showed that it can be computed using [Formula: see text] exact maxflow computations. Surprisingly, this remains the best algorithm for Gomory–Hu trees more than 50 years later, even for approximate mincuts. In this paper, we break this longstanding barrier and give an algorithm for computing a [Formula: see text]-approximate Gomory–Hu tree using [Formula: see text] maxflow computations. Specifically, we obtain the running time bounds we describe below. We obtain a randomized (Monte Carlo) algorithm for undirected, weighted graphs that runs in [Formula: see text] time and returns a [Formula: see text]-approximate Gomory–Hu tree with high probability (w.h.p.). Previously, the best running time known was [Formula: see text], which is obtained by running Gomory and Hu’s original algorithm on a cut sparsifier of the graph. Next, we obtain a randomized (Monte Carlo) algorithm for undirected, unweighted graphs that runs in [Formula: see text] time and returns a [Formula: see text]-approximate Gomory–Hu tree w.h.p. This improves on our first result for sparse graphs, namely [Formula: see text]. Previously, the best running time known for unweighted graphs was [Formula: see text] for an exact Gomory–Hu tree [A. Bhalgat et al., Proceedings of the 39 th Annual ACM Symposium on Theory of Computing, San Diego, CA, 2007, pp. 605–614]; no better result is known if approximations are allowed. As a consequence of our Gomory–Hu tree algorithms, we also solve the [Formula: see text]-approximate all-pairs mincut (APMC) and single-source mincut (SSMC) problems in the same time bounds. (These problems are simpler in that the goal is to only return the [Formula: see text]-mincut values, and not the mincuts.) This improves on the recent algorithm for these problems in [Formula: see text] time due to Abboud, Krauthgamer, and Trabelsi [2020 IEEE 61 st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 2020, pp. 105–118].