Minimum \(s\!-\!t\) Cuts with Fewer Cut Queries
Abstract
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 \subseteq V\), returns the size of the cut \((S, V\ \unicode{x005C}\ S)\).
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Computational Geometry and Mesh Generation
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 258–296
- Publication date
- 1 January 2026
- Language
- EN