Deterministic Minimum Cut in Poly-logarithmic Maximum Flows
Open Access
- 24 July 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (4) , 1-18
Abstract
We give a deterministic algorithm for finding the minimum (weight) cut of an undirected graph on n vertices and m edges using polylog ( n ) calls to a black box maximum flow subroutine. Using the current best deterministic maximum flow algorithms, this marks the first improvement for this problem since a running time bound of \(\tilde{O}(mn)\) was established by several papers in the early 1990s. Our global minimum cut algorithm is obtained as a corollary of a deterministic minimum Steiner cut algorithm, where a minimum Steiner cut is a minimum (weight) set of edges whose removal disconnects at least one pair of vertices among a designated set of terminal vertices. We also give a remarkably simple randomized minimum Steiner cut algorithm that still improves the best known randomized algorithm for the problem. Our main technical contribution is a new tool that we call isolating cuts . Given a set of vertices R , this entails finding cuts of minimum weight that separate (or isolate) each individual vertex \(v\in R\) from the rest of the vertices \(R\setminus \lbrace v\rbrace\) . Naïvely, this can be done using |R| maximum flow calls, but we show that just O (log |R| ) calls on graphs containing O(n) vertices and O(m) edges suffice. We call this the isolating cut lemma .
Keywords
Funding Information
- NSF award (CCF-1907820, CCF-1955703)
- NSF CAREER Award (CCF-1750140)
This publication has 17 references indexed in Scilit:
- Deterministic Near-Linear Time Minimum Cut in Weighted Graphs2024
- A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow2023
- Augmenting Edge Connectivity via Isolating Cuts2022
- Parameterized Algorithms2015
- A new approach to the minimum cut problemJournal of the ACM, 1996
- Color-codingJournal of the ACM, 1995
- A Matroid Approach to Finding Edge Connectivity and Packing ArborescencesJournal of Computer and System Sciences, 1995
- A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graphAlgorithmica, 1992
- Computing Edge-Connectivity in Multigraphs and Capacitated GraphsSIAM Journal on Discrete Mathematics, 1992
- Multi-Terminal Network FlowsJournal of the Society for Industrial and Applied Mathematics, 1961