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.

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.

In the cut-query model, the algorithm can access the input graph G = (V,E) only via cut queries that report, given a set S ⊆ V, the total weight of edges crossing the cut between S and V⧵ S. This model was introduced by Rubinstein, Schramm and Weinberg [ITCS'18] and its investigation has so far focused on the number of queries needed to solve optimization problems, such as global minimum cut. We turn attention to the round complexity of cut-query algorithms, and show that several classical problems can be solved in this model with only a constant number of rounds. Our main results are algorithms for finding a minimum cut in a graph, that offer different tradeoffs between round complexity and query complexity, where n = |V| and δ(G) denotes the minimum degree of G: (i) Õ(n^{4/3}) cut queries in two rounds in unweighted graphs; (ii) Õ(rn^{1+1/r}/δ(G)^{1/r}) queries in 2r+1 rounds for any integer r ≥ 1 again in unweighted graphs; and (iii) Õ(rn^{1+(1+log_n W)/r}) queries in 4r+3 rounds for any r ≥ 1 in weighted graphs. We also provide algorithms that find a minimum (s,t)-cut and approximate the maximum cut in a few rounds.