Deterministic Almost-Linear-Time Gomory-Hu Trees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908469287714816 |
|---|---|
| author | Abboud, Amir Kyng, Rasmus Li, Jason Panigrahi, Debmalya Gutenberg, Maximilian Probst Saranurak, Thatchaphol Yuan, Weixuan Yuan, Wuwei |
| author_facet | Abboud, Amir Kyng, Rasmus Li, Jason Panigrahi, Debmalya Gutenberg, Maximilian Probst Saranurak, Thatchaphol Yuan, Weixuan Yuan, Wuwei |
| contents | Given an $m$-edge, undirected, weighted graph $G=(V,E,w)$, a Gomory-Hu tree $T$ (Gomory and Hu, 1961) is a tree over the vertex set $V$ such that all-pairs mincuts in $G$ are preserved exactly in $T$.
In this article, we give the first almost-optimal $m^{1+o(1)}$-time deterministic algorithm for constructing a Gomory-Hu tree. Prior to our work, the best deterministic algorithm for this problem dated back to the original algorithm of Gomory and Hu that runs in $nm^{1+o(1)}$ time (using current maxflow algorithms). In fact, this is the first almost-linear time deterministic algorithm for even simpler problems, such as finding the $k$-edge-connected components of a graph.
Our new result hinges on two separate and novel components that each introduce a distinct set of de-randomization tools of independent interest:
- a deterministic reduction from the all-pairs mincuts problem to the single-souce mincuts problem incurring only subpolynomial overhead, and
- a deterministic almost-linear time algorithm for the single-source mincuts problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_20354 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Deterministic Almost-Linear-Time Gomory-Hu Trees Abboud, Amir Kyng, Rasmus Li, Jason Panigrahi, Debmalya Gutenberg, Maximilian Probst Saranurak, Thatchaphol Yuan, Weixuan Yuan, Wuwei Data Structures and Algorithms Given an $m$-edge, undirected, weighted graph $G=(V,E,w)$, a Gomory-Hu tree $T$ (Gomory and Hu, 1961) is a tree over the vertex set $V$ such that all-pairs mincuts in $G$ are preserved exactly in $T$. In this article, we give the first almost-optimal $m^{1+o(1)}$-time deterministic algorithm for constructing a Gomory-Hu tree. Prior to our work, the best deterministic algorithm for this problem dated back to the original algorithm of Gomory and Hu that runs in $nm^{1+o(1)}$ time (using current maxflow algorithms). In fact, this is the first almost-linear time deterministic algorithm for even simpler problems, such as finding the $k$-edge-connected components of a graph. Our new result hinges on two separate and novel components that each introduce a distinct set of de-randomization tools of independent interest: - a deterministic reduction from the all-pairs mincuts problem to the single-souce mincuts problem incurring only subpolynomial overhead, and - a deterministic almost-linear time algorithm for the single-source mincuts problem. |
| title | Deterministic Almost-Linear-Time Gomory-Hu Trees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.20354 |