Minimum Cuts in Directed Graphs via Partial Sparsification

We give an algorithm to find a minimum cut in an edge-weighted directed graph with n vertices and m edges in Õ(n • maxm 2/3 , n) time. This improves on the 30 year old bound of Õ(nm) obtained by Hao and Orlin for this problem. Using similar techniques, we also obtain Õ(n 2 / 2 )-time (1+ )-approximation algorithms for both the minimum edge and minimum vertex cuts in directed graphs, for any fixed . Before our work, no (1 + )-approximation algorithm better than the exact runtime of Õ(nm) is known for either problem.

Our algorithms follow a two-step template. In the first step, we employ a partial sparsification of the input graph to preserve a critical subset of cut values approximately. In the second step, we design algorithms to find the (edge/vertex) mincut among the preserved cuts from the first step. For edge mincut, we give a new reduction to Õ(minn/m 1/3 , √ n) calls of any maxflow subroutine, via packing arborescences in the sparsifier. For vertex mincut, we develop new local flow algorithms to identify small unbalanced cuts in the sparsified graph.

• This paper combines, and improves on, two independent manuscripts by Quanrud [Qua21] and the other authors [CLN + 21].