Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs

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 m 1+o(1) /ϵ on any m-edge n-vertex input graph, assuming all edge/vertex weights are polynomially-bounded. In particular, for any constant ϵ > 0, our algorithms have an almost-optimal running time of O m 1+o(1) . The fastest previously-known running time for this setting, due to (Cen et al., FOCS 2021), is Õ min n 2 /ϵ 2 , m 1+o(1) √ n for Minimum Edge-Cut, and Õ n 2 /ϵ 2 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.