Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs

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 Õ(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 Õ(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 mn 0.976 • poly log W where W is the ratio of largest to smallest vertex weight. Our algorithm can also be viewed as improving and significantly simplifying the recent randomized O(mn 0.99+o(1) • poly log W )-time algorithm for the undirected version of the problem (Chuzhoy and Trabelsi, STOC 2025).

Additionally, we provide a randomized O min m 1+o(1) • k, n 2+o(1) -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 Õ min k 2 • m, mn 11/12+o(1) , n 2+o(1) (Forster et al., SODA 2020, Li et al., STOC 2021). Our result almost matches the best current running time of Õ min k • m, n 2 for the directed unweighted edge-based version of the problem, due to (Gabow, STOC 1991 and J. Comput. Syst. Scie., 95) and (Chekuri, Quanrud, ICALP 2021).