Minimum s t Cuts with Fewer Cut Queries

We study the problem of computing a minimum s-t cut in an unweighted, undirected graph via cut queries. In this model, the input graph is accessed through an oracle that, given a subset of vertices S ⊆ V , returns the size of the cut (S, V S).

This line of work was initiated by Rubinstein, Schramm, and Weinberg (ITCS 2018), who gave a randomized algorithm that computes a minimum s-t cut using O(n 5/3 ) queries, thereby showing that one can avoid spending Θ(n 2 ) queries required to learn the entire graph. 1 A recent result by Anand, Saranurak, and Wang (SODA 2025) also matched this upper bound via a deterministic algorithm based on blocking flows.

In this work, we present a new randomized algorithm that improves the cut-query complexity to O(n 8/5 ). At the heart of our approach is a query-efficient subroutine that incrementally reveals the graph edge-by-edge while increasing the maximum s-t flow in the learned subgraph at a rate faster than classical augmenting-path methods. Notably, our algorithm is simple, purely combinatorial, and can be naturally interpreted as a recursive greedy procedure.

As a further consequence, we obtain a deterministic and combinatorial two-party communication protocol for computing a minimum s-t cut using O(n 11/7 ) bits of communication. This improves upon the previous best bound of O(n 5/3 ), which was obtained via reductions from the aforementioned cut-query algorithms. In parallel, it has been observed that an O(n 3/2 )-bit randomized protocol can be achieved via continuous optimization techniques; however, these methods are fundamentally different from our combinatorial approach.