Deterministic min-cut in poly-logarithmic max-flows

Conference Paper

We give a deterministic (global) min-cut algorithm for weighted undirected graphs that runs in time O(m{1+ epsilon}) plus polylog (n) max-flow computations. Using the current best max-flow algorithms, this results in an overall running time of tilde{O}(m cdot min(sqrt{m}, n{2/3})) for weighted graphs, and m{4/3+o(1)} for unweighted (multi)-graphs. This is the first improvement in the running time of deterministic algorithms for the min-cut problem on general (weighted/multi) graphs since the early 1990s when a running time bound of tilde{O}(mn) was established for this problem.

Full Text

Duke Authors

Cited Authors

  • Li, J; Panigrahi, D

Published Date

  • November 1, 2020

Published In

Volume / Issue

  • 2020-November /

Start / End Page

  • 85 - 92

International Standard Serial Number (ISSN)

  • 0272-5428

International Standard Book Number 13 (ISBN-13)

  • 9781728196213

Digital Object Identifier (DOI)

  • 10.1109/FOCS46700.2020.00017

Citation Source

  • Scopus