{"ID":2824077,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.24355","arxiv_id":"2512.24355","title":"Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs","abstract":"We study the directed global minimum vertex-cut problem: given a directed vertex-weighted graph $G$, compute a vertex-cut $(L,S,R)$ in $G$ of minimum value, which is defined to be the total weight of all vertices in $S$. The problem, together with its edge-based variant, is one of the most basic in graph theory and algorithms, and has been studied extensively. The fastest currently known algorithm for directed global minimum vertex-cut (Henzinger, Rao and Gabow, FOCS 1996 and J. Algorithms 2000) has running time $\\tilde{O}(mn)$, where $m$ and $n$ denote the number of edges and vertices in the input graph, respectively. A long line of work over the past decades led to faster algorithms for other main versions of the problem, including the undirected edge-based setting (Karger, STOC 1996 and J. ACM 2000), directed edge-based setting (Cen et al., FOCS 2021), and undirected vertex-based setting (Chuzhoy and Trabelsi, STOC 2025). However, for the vertex-based version in directed graphs, the 29 year-old $\\tilde{O}(mn)$-time algorithm of Henzinger, Rao and Gabow remains the state of the art to this day, in all edge-density regimes. In this paper we break the $Θ(mn)$ running time barrier for the first time, by providing a randomized algorithm for directed global minimum vertex-cut, with running time $O\\left(mn^{0.976}\\cdot\\operatorname{polylog} W\\right)$ where $W$ is the ratio of largest to smallest vertex weight. Additionally, we provide a randomized $O\\left(\\min\\left\\{m^{1+o(1)}\\cdot k,n^{2+o(1)}\\right\\}\\right)$-time algorithm for the unweighted version of directed global minimum vertex-cut, where $k$ is the value of the optimal solution. The best previous algorithm for the problem achieved running time $\\tilde O\\left(\\min\\left\\{k^2 \\cdot m, mn^{11/12+o(1)}, n^{2+o(1)}\\right\\}\\right)$ (Forster et al., SODA 2020, Li et al., STOC 2021).","short_abstract":"We study the directed global minimum vertex-cut problem: given a directed vertex-weighted graph $G$, compute a vertex-cut $(L,S,R)$ in $G$ of minimum value, which is defined to be the total weight of all vertices in $S$. The problem, together with its edge-based variant, is one of the most basic in graph theory and alg...","url_abs":"https://arxiv.org/abs/2512.24355","url_pdf":"https://arxiv.org/pdf/2512.24355v1","authors":"[\"Julia Chuzhoy\",\"Ron Mosenzon\",\"Ohad Trabelsi\"]","published":"2025-12-30T17:06:30Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}