{"ID":2847541,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.27330","arxiv_id":"2510.27330","title":"A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition","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 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.","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 and efficient randomized reduction from Gomory-Hu trees to polylog maxflow computations. On unweighted graphs, our reduction reduces to maxflow computat...","url_abs":"https://arxiv.org/abs/2510.27330","url_pdf":"https://arxiv.org/pdf/2510.27330v2","authors":"[\"Maximilian Probst Gutenberg\",\"Weixuan Yuan\"]","published":"2025-10-31T10:01:08Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}