A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911621699338240 |
|---|---|
| author | Gutenberg, Maximilian Probst Yuan, Weixuan |
| author_facet | Gutenberg, Maximilian Probst Yuan, Weixuan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_27330 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition Gutenberg, Maximilian Probst Yuan, Weixuan Data Structures and Algorithms 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. |
| title | A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.27330 |