Deterministic Global Minimum Cut Using $\tilde{O}(n^{3\mathrm{/}2})$ Cut Queries

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 $\tilde{O}(n)$ queries, known deterministic algorithms use $\tilde{O}(n^{5\mathrm{/}3})$ queries. We improve upon this result and give a simple deterministic algorithm that finds a global minimum cut using $\tilde{O}(\min \{n\delta ,n^2\mathrm{/}\delta \})$ cut queries, which equals $\tilde{O}(n^{3\mathrm{/}2})$ in the worst case, where $\delta$ is the minimum degree of the graph. The key ingredient in our approach is an efficient maximum $s,t$-flow algorithm, for the case when the minimum $s,t$-cut has value at most $\delta$.