Deterministic Minimum Cut in Poly-logarithmic Maximum Flows

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 Õ(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 ∈ R from the rest of the vertices R \ {v}. 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.

Duke Scholars

Author Debmalya Panigrahi Computer Science