Cut-Query Algorithms with Few Rounds

Yotam Kenneth-Mordoch, Robert Krauthgamer

Introduction

In graph theory, the minimum cut (min-cut) problem is a cornerstone of combinatorial optimization. Traditionally, algorithms for finding the min-cut assume full access to the graph's adjacency list or matrix. However, in many modern contexts—ranging from submodular optimization to data streaming—access is restricted. This paper, "Cut-Query Algorithms with Few Rounds" by Yotam Kenneth-Mordoch and Robert Krauthgamer, investigates the efficiency of finding the global minimum cut when the graph is accessible only through a cut-query oracle. Specifically, the authors focus on the trade-off between the total number of queries and the number of interaction rounds (adaptivity) required to solve the problem.

The Cut-Query Model and Round Complexity

In the cut-query model, the algorithm does not see edges directly. Instead, it queries a set of vertices $S \subset V$, and the oracle returns the weight of the cut $\partial(S)$, which is the sum of the weights of all edges with exactly one endpoint in $S$. This model is particularly significant because the cut function is a fundamental example of a symmetric submodular function.

While previous literature has extensively explored query complexity (the total number of calls to the oracle), this work prioritizes round complexity. In a single round, an algorithm can issue multiple queries in parallel, but the choice of queries in round $i+1$ can only depend on the results from round $i$. Minimizing rounds is crucial for parallel computing and streaming applications, where the number of rounds often corresponds to the number of passes over a dataset. Prior to this work, most algorithms required $O(\log n)$ or $O(n)$ rounds; Kenneth-Mordoch and Krauthgamer demonstrate that near-optimal results can be achieved in constant or near-constant rounds.

Algorithmic Innovations

To bypass the sequential nature of traditional min-cut algorithms (like those based on binary search), the authors introduce three primary technical innovations:

1. Parallel Edge Sampling via Sparse Recovery

Standard edge sampling techniques often rely on sequential processes to identify edges. The authors adapt techniques from compressed sensing and streaming—specifically sparse recovery and Count-Min sketches. By partitioning vertices into multiple levels and applying linear-algebraic recovery methods, they can sample edges in just 1 or 2 rounds, effectively "learning" the graph's structure in parallel.

2. $\tau$-Star Contraction

Graph contraction is a common strategy to reduce the search space for a min-cut. However, standard methods focus on reducing the number of vertices. The authors propose $\tau$-star contraction, a novel method designed to reduce the number of edges. By shrinking the edge count, the algorithm eventually reaches a state where the remaining graph is sparse enough to be fully reconstructed and solved in a single final round of queries.

For weighted graphs, the authors reduce the problem to finding the minimum element in a monotone matrix. They develop a recursive strategy that partitions the matrix into $n^{1/r}$ blocks. This allows the search to be completed in exactly $r$ rounds, providing a flexible framework for balancing rounds against query count.

Key Results

The paper establishes several new upper bounds for both unweighted and weighted graphs:

  • Unweighted Graphs (2 Rounds): The authors provide an algorithm that finds the min-cut in just 2 rounds using $\tilde{O}(n^{4/3})$ queries. This is a significant improvement over the naive $O(n^2)$ approach.
  • Unweighted Trade-offs: For any integer $r$, the min-cut can be found in $2r+1$ rounds using $\tilde{O}(n^{1+1/r})$ queries. As $r$ increases, the query complexity approaches the theoretical lower bound of $\tilde{O}(n)$.
  • Weighted Graphs: The authors achieve a similar trade-off for weighted graphs, finding the min-cut in $O(r)$ rounds with a corresponding query complexity.
  • Streaming Efficiency: These results imply that the global minimum cut can be found in a constant number of passes over a data stream with limited memory, a major step forward for dynamic graph processing.

Conclusion and Future Directions

Kenneth-Mordoch and Krauthgamer demonstrate that the symmetry of the cut function allows for much higher adaptivity than general submodular minimization. By integrating sparse recovery with novel contraction methods, they provide the first constant-round algorithms for the min-cut problem in the cut-query model.

Future research remains to be done in establishing lower bounds to determine if these query/round trade-offs are optimal. Additionally, while these algorithms are randomized, the development of a deterministic constant-round algorithm remains an open challenge in the field.

Summary updated

BibTeX
@inproceedings{kennethmordoch2025cut,
  author = {Yotam Kenneth-Mordoch and Robert Krauthgamer},
  title = {{Cut-Query Algorithms with Few Rounds}},
  booktitle = {Esa},
  year = {2025},
  doi = {10.4230/lipics.esa.2025.100},
}
Figure