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 \(\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 .