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(m1+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(m1+o(1)). The fastest previously-known running time for this setting, due to (Cen et al., FOCS 2021), is O(min{n2/є2,m1+o(1)√n}) for Minimum Edge-Cut, and O(n2/є2) for Minimum Vertex-Cut.