A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows

Given an undirected graph G = (V, E, w), a Gomory-Hu tree T (Gomory and Hu, 1961) is a tree on V that preserves all-pairs mincuts of G exactly.

We present a simple, efficient reduction from Gomory-Hu trees to polylog maxflow computations. On unweighted graphs, our reduction reduces to maxflow computations on graphs of total instance size Õ(m) 1 and the algorithm requires only Õ(m) additional time. Our reduction is the first that is tight up to polylog factors. The reduction also seamlessly extends to weighted graphs, however, instance sizes and runtime increase to Õ(n 2 ).

Finally, we show how to extend our reduction to reduce Gomory-Hu trees for unweighted hypergraphs to maxflow in hypergraphs. Again, our reduction is the first that is tight up to polylog factors.

The research leading to these results has received funding from grant no. 200021 204787 of the Swiss National Science Foundation.

† The research leading to these results has received funding from the starting grant "A New Paradigm for Flow and Cut Algorithms" (no. TMSGI2 218022) of the Swiss National Science Foundation.

1 Adhering to convention, throughout, we denote by m the number of edges of the input graph G and by n the number of vertices. We use Õ(•)-notation to hide logarithmic factors in n, m and W .