Deterministic method finds minimum cuts in weighted graphs efficiently
Finding and Certifying Weighted Minimum Cuts with Cut Queries
Data Structures and Algorithms
Summary
Finding the smallest way to cut a network so it splits into parts is a classic problem in computer science. The authors developed new techniques that let computers check the smallest cut using fewer questions about the network's structure, working even when edges have different weights. They show both how to quickly verify a minimum cut and how to find one directly using clever shortcuts and carefully built simpler graphs. This improves the efficiency of known methods, especially for complicated weighted networks.
What this means in practice
- •For network engineers: Check the robustness of weighted network designs faster by identifying exact minimum cuts with fewer queries to the network structure.
- •For data center operators: Improve fault detection by certifying minimal cut capacities in data center topologies using explicit deterministic query procedures.
A theory result. No direct application yet.
Authors
Troy Lee
Abstract
We study the deterministic and nondeterministic cut query complexity of minimum cut in undirected graphs with arbitrary nonnegative edge weights. For the nondeterministic case, we show that every $n$-vertex graph has an $O(n\log^2(2n))$-query certificate of its exact global minimum-cut value, such that any other nonnegatively weighted graph on the same vertex set that agrees on these queries has the same minimum cut value. A key ingredient is a way to certify a maximum $s$--$t$ flow value with only $O(n)$ cut queries. For the deterministic case we give an algorithm that finds an exact global minimum cut using $O(n^{3/2}\log^3(2n)(\log\log(2n))^2)$ cut queries. Previously no $O(n^{2-\varepsilon})$ deterministic bound was known for arbitrary nonnegatively weighted graphs. The algorithm follows Karger's two-respecting tree approach. The key new ingredient is a deterministic construction of a weak skeleton of the input graph $G$: an explicit weighted graph $H$ in which every minimum cut of $G$ is a $5/4$-approximate minimum cut.