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 tildeO(n\max\{m 2/3}, n\}) time. This improves on the 30 year old bound of tildeO(nm) obtained by Hao and Orlin for this problem. Using similar techniques, we also obtain tildeO(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 tildeO(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 tildeO(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.
