{"ID":2875553,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.02520","arxiv_id":"2509.02520","title":"A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2509.02520","url_pdf":"https://arxiv.org/pdf/2509.02520v2","authors":"[\"Maximilian Probst Gutenberg\",\"Rasmus Kyng\",\"Weixuan Yuan\",\"Wuwei Yuan\"]","published":"2025-09-02T17:15:45Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}