Approximate Gomory-Hu tree is faster than n - 1 max-flows

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 Õ( m + n 3/2 ) time and returns a (1+є)-approximate Gomory-Hu tree algorithm whp. Previously, the best running time known was Õ( 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 algorithm whp. 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 Õ( 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 Õ( n 2 ) time due to Abboud et al. (FOCS 2020).

Authors

• Jason Li 0006
• Debmalya Panigrahi

Keywords

• Gomory-Hu tree
• graph algorithm
• graph connectivity