Deterministic algorithm improves global minimum cut queries to n to the three halves
Deterministic Global Minimum Cut Using $\tilde{O}(n^{3/2})$ Cut Queries
Data Structures and Algorithms
Summary
Finding the smallest set of edges that splits a network into two parts is a key problem in computer science. There is a fast but random method to do this, and slower methods that always work but take more tries. The authors created a new approach that is always reliable and faster than old deterministic methods, using fewer checks on the network connections. They use a special trick involving network flow calculation to achieve this improvement.
What this means in practice
- •For network design engineers: Optimize network resilience analysis by deterministically identifying critical cuts in communication networks with fewer queries.
- •For software developers for graph analytics: Implement faster deterministic routines for global minimum cut detection in unweighted graphs to improve graph processing tools.
Authors
Yotam Kenneth-Mordoch
Abstract
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/3})$ queries. We improve upon this result and give a simple deterministic algorithm that finds a global minimum cut using $\tilde O(\min\left\{ nδ,n^2/δ\right\})$ cut queries, which equals $\tilde{O}(n^{3/2})$ in the worst case, where $δ$ 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 $δ$.