A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
This work provides the first tight (up to polylog factors) reduction for Gomory-Hu trees, benefiting algorithms for all-pairs mincuts.
The paper presents a reduction from Gomory-Hu trees to polylog maxflow computations, achieving near-optimal runtime on unweighted graphs with total instance size Õ(m) and Õ(m) additional time, and extends to weighted graphs and hypergraphs.
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 $\tilde{O}(m)$ and the algorithm requires only $\tilde{O}(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 $\tilde{O}(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.