Minimum s s – t t Cuts with Fewer Cut Queries

Yonggang Jiang, Danupon Nanongkai, Pachara Sawettamalya · 2025

Read Minimum s s – t t Cuts with Fewer Cut Queries by Yonggang Jiang, Danupon Nanongkai, Pachara Sawettamalya (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-18274.txt.

Introduction

Yonggang Jiang, with Danupon Nanongkai and Pachara Sawettamalya, improves minimum cut finding in a 2025 paper. A minimum s-t cut is the cheapest set of links whose removal separates two chosen points. The graph stays hidden behind cut queries, questions that report how many links cross a chosen split.

Older methods needed many more queries than the new randomized algorithm does. Its subroutine reveals the graph edge by edge while growing flow faster than classic step-by-step methods. The approach stays simple, purely combinatorial, meaning it counts and compares discrete structures only. The team also derives a cheaper two-party communication protocol from the same idea.

Catalog record

CREATORYonggang Jiang, Danupon Nanongkai, Pachara Sawettamalya
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE136 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-18274

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Minimum s s – t t Cuts with Fewer Cut Queries Yonggang Jiang, Danupon Nanongkai, Pachara Sawettamalya Abstract We study the problem of computing a minimum s s – t 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 S\subseteq V , returns the size of the cut ( S , V ∖ S ) (S,V\setminus S) . This line of work was initiated by Rubinstein, Schramm, and Weinberg (ITCS 2018), who gave a randomized algorithm that computes a minimum s s – t t cut using O ~ ​ ( n 5 / 3 ) \widetilde{O}(n^{5/3}) queries, thereby showing that one can avoid spending Θ ~ ​ ( n 2 ) \widetilde{\Theta}(n^{2}) queries required to learn the entire graph. 1 1 1 Throughout this work, we use O ~ ​ ( ⋅ ) \widetilde{O}(\cdot) , Θ ~ ​ ( ⋅ ) \widetilde{\Theta}(\cdot) , Ω ~ ​ ( ⋅ ) \widetilde{\Omega}(\cdot) , and ω ~ ​ ( ⋅ ) \widetilde{\omega}(\cdot) to hide suitable polylog ⁡ ( n ) \mathrm{polylog}(n) factors. 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 ) \widetilde{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 s – t 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 s – t t cut using O ~ ​ ( n 11 / 7 ) \widetilde{O}(n^{11/7}) bits of communication. This improves upon the previous best bound of O ~ ​ ( n 5 / 3 ) \widetilde{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 ) \widetilde{O}(n^{3/2}) -bit randomized protocol can be achieved via continuous optimization techniques; however, these methods are fundamentally different from our combinatorial approach. 1 Introduction The minimum s – t cut problem is a cornerstone of combinatorial optimization and graph algorithms. Formally, given an undirected, unweighted graph G=(V,E) on n vertices, along with two distinguished terminals s,t\in V , the goal is to compute an s – t cut of the vertex set—that is, a partition (S,T) with s\in S and t\in T —that minimizes the number of edges crossing the cut, i.e., the quantity |E(S,T)|:=|E\cap(S\times T)| . In this work, we study the complexity of computing a minimum s – t cut in two computational models that restrict access to the input graph. Cut-query. In this setting, we may query an oracle with a partition (S,T) of V (i.e. a cut ) to obtain the cut value |E(S,T)| . Our goal is to compute a minimum s - t cut of G while minimizing the total number of queries made to the oracle. This problem was first introduced by the work of Rubinstein, Schramm, and Weinberg [ RSW18 ] in an effort to study submodular function minimization problem. 2 2 2 The problem was in fact studied earlier by Cunningham [ Cun85 ] who observed that the problem can be solved in \widetilde{O}(n^{2}) queries even on weighted directed graphs. Note, however, that the \widetilde{O}(n^{2}) query complexity is trivial for undirected graphs. While the “trivial” O(n^{2}) queries suffices to learn the whole undirected graph, the work of [ RSW18 ] were the first to break this quadratic barrier via an \widetilde{O}(n^{5/3}) -query algorithm utilizing the randomized construction of a cut sparsifier. More recently, Anand, Saranurak, and Wang [ ASW25 ] developed a new deterministic algorithm, matching the same \widetilde{O}(n^{5/3}) query complexity. Notably, their approach is purely combinatorial via an implementation of Dinitz’s blocking flow algorithm [ Din70 ] , thereby is vastly different from the techniques deployed in [ RSW18 ] . Nevertheless, both algorithms circumvent the necessity to learn the whole graph which information-theoretically require \widetilde{\Omega}(n^{2}) queries to the oracle when the graph is dense. The works of Rubinstein, Schramm, and Weinberg [ RSW18 ] and Anand, Saranurak, and Wang [ ASW25 ] approach the s – t minimum cut problem from two completely orthogonal perspectives; yet both arrive at algorithms with the same query complexity of \widetilde{O}(n^{5/3}) . This convergence naturally raises the question: Do the current \widetilde{O}(n^{5/3}) -query upper bounds represent a latent barrier for computing a minimum s - t cut? In this work, we show that we can indeed go below this bound. Theorem 1.1 (Main result #1) . There is a randomized algorithm that computes a minimum s - t cut of an undirected unweighted graph G . The algorithm always makes \widetilde{O}(n^{8/5}) cut queries to G and succeeds with high probability. In addition, our algorithm can be extended to enumerate all minimum s – t cuts within the same query complexity, although we do not make this extension explicit in our later analysis. We also highlight that our algorithms are simple, purely combinatorial, and can be naturally interpreted as a recursive greedy procedure. Two-player communication. In this setting, input graph G=(V,E) is edge-partitioned across two players, namely Alice has G_{A}=(V,E_{A}) , and Bob has G_{B}=(V,E_{B}) , with E=E_{A}\cup E_{B} . The players are allowed to exchange a sequence of messages (via a protocol ) with the goal of computing a minimum s - t cut of G while minimizing the total amount of communication between the players. In fact, any upper bound in the cut-query model translates to an upper bound in the communication setting, with an additional O(\log n) factor. To see this, observe that any cut query can be simulated with O(\log n) bits of communication: Alice locally computes |E_{A}(S,T)| and sends the result to Bob, who then computes |E_{B}(S,T)| and sends it back to Alice. The players can thus recover the cut value by computing |E(S,T)|=|E_{A}(S,T)|+|E_{B}(S,T)| . Since both |E_{A}(S,T)| and |E_{B}(S,T)| are bounded by O(n^{2}) , they can each be represented with O(\log n) bits, making the communication cost per query O(\log n) . As an immediate corollary, simulating the deterministic \widetilde{O}(n^{5/3}) -query algorithm of Anand, Saranurak, and Wang [ ASW25 ] yields a deterministic communication protocol with total cost \widetilde{O}(n^{5/3}) bits. Furthermore, although the algorithm of Rubinstein, Schramm, and Weinberg [ RSW18 ] is originally randomized in the cut-query setting, it can be derandomized in the communication model, resulting in the same \widetilde{O}(n^{5/3}) deterministic upper bound. To our knowledge, prior to this work, no subquadratic deterministic or combinatorial protocol for computing a minimum s – t cut is known beyond simulating one of these cut-query algorithms. As a by-product of 1.1 , our \widetilde{O}(n^{1.6}) -query algorithm immediately yields a two-player communication protocol with total communication cost of \widetilde{O}(n^{1.6}) bits. Furthermore, through a careful implementation of our algorithm, we obtain a deterministic

Read the complete text