All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries

Abstract

We present the first non-trivial algorithm for the all-pairs minimum cut problem in the cut-query model. Given cut-query access to an unweighted graph $G=(V,E)$ with $n$ vertices, our randomized algorithm constructs a Gomory-Hu tree of $G$, and thus solves the all-pairs minimum cut problem, using $\tilde{O}(n^{7/4})$ cut queries.