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 \(\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.