{"ID":2831377,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.09080","arxiv_id":"2512.09080","title":"Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs","abstract":"We develop new $(1+ε)$-approximation algorithms for finding the global minimum edge-cut in a directed edge-weighted graph, and for finding the global minimum vertex-cut in a directed vertex-weighted graph. Our algorithms are randomized, and have a running time of $O\\left(m^{1+o(1)}/ε\\right)$ on any $m$-edge $n$-vertex input graph, assuming all edge/vertex weights are polynomially-bounded. In particular, for any constant $ε\u003e0$, our algorithms have an almost-optimal running time of $O\\left(m^{1+o(1)}\\right)$. The fastest previously-known running time for this setting, due to (Cen et al., FOCS 2021), is $\\tilde{O}\\left(\\min\\left\\{n^2/ε^2,m^{1+o(1)}\\sqrt{n}\\right\\}\\right)$ for Minimum Edge-Cut, and $\\tilde{O}\\left(n^2/ε^2\\right)$ for Minimum Vertex-Cut. Our results further extend to the rooted variants of the Minimum Edge-Cut and Minimum Vertex-Cut problems, where the algorithm is additionally given a root vertex $r$, and the goal is to find a minimum-weight cut separating any vertex from the root $r$. In terms of techniques, we build upon and extend a framework that was recently introduced by (Chuzhoy et al., SODA 2026) for solving the Minimum Vertex-Cut problem in unweighted directed graphs. Additionally, in order to obtain our result for the Global Minimum Vertex-Cut problem, we develop a novel black-box reduction from this problem to its rooted variant. Prior to our work, such reductions were only known for more restricted settings, such as when all vertex-weights are unit.","short_abstract":"We develop new $(1+ε)$-approximation algorithms for finding the global minimum edge-cut in a directed edge-weighted graph, and for finding the global minimum vertex-cut in a directed vertex-weighted graph. Our algorithms are randomized, and have a running time of $O\\left(m^{1+o(1)}/ε\\right)$ on any $m$-edge $n$-vertex...","url_abs":"https://arxiv.org/abs/2512.09080","url_pdf":"https://arxiv.org/pdf/2512.09080v2","authors":"[\"Ron Mosenzon\"]","published":"2025-12-09T19:51:45Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}