# Computing exact minimum cuts without knowing the graph

arXiv: https://arxiv.org/abs/1711.03165 · HTML: https://mlsanity.com/paper/1711.03165/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2017.

## Built on by (most cited first, 3 of 3)

- [Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods](https://mlsanity.com/paper/2310.05309/) (2023)
- [Clustering with Non-adaptive Subset Queries](https://mlsanity.com/paper/2409.10908/) (2024)
- [Learning Partitions with Optimal Query and Round Complexities](https://mlsanity.com/paper/2505.05009/) (2025)

## Abstract (arXiv)

We give query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs. Our oracle model is inspired by the submodular function minimization problem: on query S subset V, the oracle returns the size of the cut between S and V setminus S. We provide algorithms computing an exact minimum s-t cut in G with tildeO(n5/3) queries, and computing an exact global minimum cut of G with only tildeO(n) queries (while learning the graph requires tildeTheta(n2) queries).