## Approximate Gomory Hu Tree Is Faster Than n - 1 Max-Flows

Publication ,  Conference
Li, J; Panigrahi, D
Published in: Proceedings of the Annual ACM Symposium on Theory of Computing
June 15, 2021

The Gomory-Hu tree or cut tree (Gomory and Hu, 1961) 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 log(n) maxflow computations. Specifically, we obtain the runtime bounds we describe below. We obtain a randomized (Monte Carlo) algorithm for undirected, weighted graphs that runs in O(m + n3/2) time and returns a (1+?)-approximate Gomory-Hu tree algorithm whp. Previously, the best running time known was O(n5/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 m4/3+o(1) time and returns a (1+?)-approximate Gomory-Hu tree algorithm whp. This improves on our first result for sparse graphs, namely m = o(n9/8). Previously, the best running time known for unweighted graphs was O(mn) for an exact Gomory-Hu tree (Bhalgat et al., STOC 2007); no better result was known if approximations are allowed. As a consequence of our Gomory-Hu tree algorithms, we also solve the (1+?)-approximate all pairs mincut and single source mincut 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(n2) time due to Abboud et al. (FOCS 2020).

## Published In

Proceedings of the Annual ACM Symposium on Theory of Computing

0737-8017

June 15, 2021

## Start / End Page

1738 / 1748

### Citation

APA
Chicago
ICMJE
MLA
NLM
Li, J., & Panigrahi, D. (2021). Approximate Gomory Hu Tree Is Faster Than n - 1 Max-Flows. In Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 1738–1748). https://doi.org/10.1145/3406325.3451112
Li, J., and D. Panigrahi. “Approximate Gomory Hu Tree Is Faster Than n - 1 Max-Flows.” In Proceedings of the Annual ACM Symposium on Theory of Computing, 1738–48, 2021. https://doi.org/10.1145/3406325.3451112.
Li J, Panigrahi D. Approximate Gomory Hu Tree Is Faster Than n - 1 Max-Flows. In: Proceedings of the Annual ACM Symposium on Theory of Computing. 2021. p. 1738–48.
Li, J., and D. Panigrahi. “Approximate Gomory Hu Tree Is Faster Than n - 1 Max-Flows.” Proceedings of the Annual ACM Symposium on Theory of Computing, 2021, pp. 1738–48. Scopus, doi:10.1145/3406325.3451112.
Li J, Panigrahi D. Approximate Gomory Hu Tree Is Faster Than n - 1 Max-Flows. Proceedings of the Annual ACM Symposium on Theory of Computing. 2021. p. 1738–1748.

## Published In

Proceedings of the Annual ACM Symposium on Theory of Computing

0737-8017

June 15, 2021

1738 / 1748