{"ID":2889973,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.20354","arxiv_id":"2507.20354","title":"Deterministic Almost-Linear-Time Gomory-Hu Trees","abstract":"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.","short_abstract":"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-H...","url_abs":"https://arxiv.org/abs/2507.20354","url_pdf":"https://arxiv.org/pdf/2507.20354v1","authors":"[\"Amir Abboud\",\"Rasmus Kyng\",\"Jason Li\",\"Debmalya Panigrahi\",\"Maximilian Probst Gutenberg\",\"Thatchaphol Saranurak\",\"Weixuan Yuan\",\"Wuwei Yuan\"]","published":"2025-07-27T16:59:40Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}