APPROXIMATE GOMORY-HU TREE IS FASTER THAN n-1 MAXIMUM FLOWS

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 (s, t)-mincuts (and by duality, the values of (s, t)-maxflows) for all-pairs of vertices s and t in an undirected graph. Gomory and Hu showed that it can be computed using n 1 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 (1+ϵ)-approximate Gomory-Hu tree using polylog(n) 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 O(m+n^3/2) time and returns a (1+ϵ)-approximate Gomory- Hu tree with high probability (w.h.p.). Previously, the best running time known was O(n^5/2), 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 m^4/3+o(1)time and returns a (1 + ϵ)-approximate Gomory-Hu tree w.h.p. This improves on our first result for sparse graphs, namely m = o(n^9/8). Previously, the best running time known for unweighted graphs was O(mn) for an exact Gomory-Hu tree [A. Bhalgat et al., Proceedings of the 39th 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 (1+ϵ)-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 (s, t)-mincut values, and not the mincuts.) This improves on the recent algorithm for these problems in O(n²) time due to Abboud, Krauthgamer, and Trabelsi [2020 IEEE 61st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 2020, pp. 105-118].

Duke Scholars

Author Debmalya Panigrahi Computer Science