Deterministic Global Minimum Cut Using Cut Queries
In the authors' words
Finding a global minimum cut in an unweighted graph is a fundamental task in the cut-query model. While there exists a randomized algorithm for this task using queries, known deterministic algorithms use queries. We improve upon this result and give a simple deterministic algorithm that finds a global minimum cut using cut queries, which equals in the worst case, where is the minimum degree of the graph. The key ingredient in our approach is an efficient maximum -flow algorithm, for the case when the minimum -cut has value at most .
Main resultThe abstract does not state a limitation.
Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: Accepted at SOSA 2027