Abstract
The minimum cut problem is a cornerstone of combinatorial optimization. While randomized algorithms have achieved near-linear time complexity for decades, deterministic algorithms for general weighted graphs remained significantly slower. This paper introduces a deterministic algorithm that reduces the global minimum cut problem to a polylogarithmic number of maximum flow calls, achieving a complexity of $\tilde{O}(m \cdot \min(\sqrt{m}, n^{2/3}))$ and bridging a long-standing gap in graph theory.
Introduction
The minimum cut (min-cut) problem seeks the smallest set of edges, by total weight, whose removal disconnects an undirected graph. Since the 1990s, a significant performance gap has existed between randomized and deterministic approaches. David Karger's Monte Carlo methods can find the min-cut in near-linear time ($O(m \log^3 n)$), but deterministic algorithms for weighted graphs were historically stuck at $\tilde{O}(mn)$. This work presents the first deterministic improvement in 30 years for this class of graphs.
The Isolating Cut Lemma
The primary technical innovation of this work is the Isolating Cut Lemma. In traditional approaches like the Gomory-Hu algorithm, finding a min-cut requires $n-1$ max-flow calls. The authors demonstrate that for any set of "terminal" vertices $R$, the minimum cuts separating each vertex in $R$ from the rest of $R$ can be found using only $O(\log |R|)$ max-flow calls.
This is achieved through a bit-wise partitioning strategy. By considering the binary representation of vertex indices, the algorithm can group terminals such that for any pair, there is at least one partition where they are separated. This "max-flow agnostic" strategy allows the algorithm to treat the underlying max-flow solver as a black box.
Algorithmic Framework
The algorithm handles the global min-cut by distinguishing between two structural scenarios:
- Unbalanced Cuts: These occur when one side of the min-cut contains very few vertices. The Isolating Cut Lemma is particularly effective here, as it can efficiently separate small sets of terminals.
- Balanced Cuts: When both sides of the cut contain many vertices, the algorithm employs expander decomposition. By partitioning the graph into well-connected clusters (expanders), the authors can sparsify the set of terminals and reduce the problem back to a variant of the unbalanced case.
To ensure the algorithm remains 100% deterministic, the authors replace random sampling techniques with a combinatorial structure known as a "splitter." This de-randomization ensures correctness without the significant performance penalties typical of earlier deterministic methods.
Key Results and Complexity
The reduction of the global min-cut problem to $\text{polylog}(n)$ max-flow calls yields substantial speedups:
- Weighted Graphs: The running time is improved to $\tilde{O}(m \cdot \min(\sqrt{m}, n^{2/3}))$.
- Unweighted Multi-graphs: The complexity reaches $m^{4/3+o(1)}$.
- Steiner Min-Cut: The paper also advances the randomized state-of-the-art for the Steiner min-cut problem (separating a specific subset of terminals) to $m^{1+o(1)}$ time.
Conclusion and Future Work
This research represents a major milestone in deterministic graph algorithms. While the polylogarithmic overhead remains a factor, the techniques introduced—particularly the Isolating Cut Lemma—have paved the way for even faster algorithms. Notably, subsequent work by Jason Li has built upon these foundations to achieve deterministic near-linear time ($O(m \cdot \text{polylog } n)$). A remaining open challenge is breaking the $n-1$ max-flow barrier for the "all-pairs" min-cut problem, represented by the Gomory-Hu tree.
Summary updated