Minimum Cuts in Directed Graphs via Partial Sparsification

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Cen, R; Li, J; Nanongkai, D; Panigrahi, D; Saranurak, T; Quanrud, K

Published Date

  • January 1, 2022

Published In

Volume / Issue

  • 2022-February /

Start / End Page

  • 1147 - 1158

International Standard Serial Number (ISSN)

  • 0272-5428

International Standard Book Number 13 (ISBN-13)

  • 9781665420556

Digital Object Identifier (DOI)

  • 10.1109/FOCS52979.2021.00113

Citation Source

  • Scopus