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 polylog(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 w.h.p. 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 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 Õ(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 (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 Õ(n 2 ) time due to Abboud et al. (FOCS 2020).