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

Conference Paper

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).

Full Text

Duke Authors

Cited Authors

  • Li, J; Panigrahi, D

Published Date

  • June 15, 2021

Published In

Start / End Page

  • 1738 - 1748

International Standard Serial Number (ISSN)

  • 0737-8017

International Standard Book Number 13 (ISBN-13)

  • 9781450380539

Digital Object Identifier (DOI)

  • 10.1145/3406325.3451112

Citation Source

  • Scopus