Approximate Gomory-Hu Tree Is Faster Than $n-1$ Max-Flows

Understand

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+\epsilon)$-approximate Gomory-Hu tree using $\text{polylog}(n)$ maxflow computations.