A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917433904726016 |
|---|---|
| author | Gutenberg, Maximilian Probst Kyng, Rasmus Yuan, Weixuan Yuan, Wuwei |
| author_facet | Gutenberg, Maximilian Probst Kyng, Rasmus Yuan, Weixuan Yuan, Wuwei |
| 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, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02520 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows Gutenberg, Maximilian Probst Kyng, Rasmus Yuan, Weixuan Yuan, Wuwei 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, 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. |
| title | A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.02520 |