A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
For researchers in graph algorithms, this provides the first tight reduction for Gomory-Hu trees, simplifying and improving the efficiency of computing all-pairs mincuts.
This paper presents a randomized reduction from Gomory-Hu tree computation to polylog maxflow computations, achieving tight bounds up to polylog factors for unweighted graphs and hypergraphs. On unweighted graphs, the total instance size is Õ(m) with Õ(m) additional time.
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 and efficient randomized 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.