Deterministic Min-cut in Poly-logarithmic Max-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 any maximum flow subroutine. Using the current best deterministic maximum flow algorithms, this yields an overall running time of Õ(m • min( √ m, n 2/3 )) for weighted graphs, and m 4/3+o(1) for unweighted (multi)-graphs. 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 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. The running time of our deterministic minimum Steiner cut algorithm matches that of the global minimum cut algorithm stated above. Using randomization, the running time improves to m 1+o(1) because of a faster maximum flow subroutine; this improves the best known randomized algorithm for the minimum Steiner cut problem as well.

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|) suffice for finding isolating cuts for any set of vertices R. We call this the isolating cut lemma.