Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow

All-Pairs Minimum Cut (APMC) is a fundamental graph problem that asks to find a minimum s, t-cut for every pair of vertices s, t. A recent line of work on fast algorithms for APMC has culminated with a reduction of APMC to polylog(n)-many max-flow computations. But unfortunately, no fast algorithms are currently known for exact max-flow in several standard models of computation, such as the cut-query model and the fully-dynamic model.

Our main technical contribution is a sparsifier that preserves all minimum s, t-cuts in an unweighted graph, and can be constructed using only approximate max-flow computations. We then use this sparsifier to devise new algorithms for APMC in unweighted graphs in several computational models: (i) a randomized algorithm that makes Õ(n 3/2 ) cut queries to the input graph; (ii) a deterministic fully-dynamic algorithm with n 3/2+o(1) worst-case update time; and (iii) a randomized two-pass streaming algorithm with space requirement Õ(n 3/2 ). These results improve over the known bounds, even for (single pair) minimum s, t-cut in the respective models.