All-Pairs Minimum Cut using \(\tilde O(n^{7/4})\) Cut Queries
Abstract
We present the first non-trivial algorithm for the all-pairs minimum cut problem in the cut-query model. Given cut-query access to an unweighted graph \(G = (V,E)\) with \(n\) vertices, our randomized algorithm constructs a Gomory-Hu tree of \(G\), and thus solves the all-pairs minimum cut problem, using \(\tilde O(n^{7/4})\) cut queries.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Facility Location and Emergency Management
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 4077–4095
- Publication date
- 1 January 2026
- Language
- EN