Faster Minimum k-Cut II: Improved Randomized and Deterministic Algorithms for Weighted Graphs
cs.DS
Submitted: 2026-08-17
Updated: 2026-11-01
License: http://creativecommons.org/licenses/by/4.0/
The gist: The Minimum k-Cut problem asks for a minimum-weight set of edges whose removal leaves an undirected weighted graph with at least k connected components.
Terminology
Abstract
The Minimum k-Cut problem asks for a minimum-weight set of edges whose removal leaves an undirected weighted graph with at least k connected components. We consider only k at least3. The fastest previous algorithm for weighted graphs ran in n k-2(m+n)(n) O(k 2) randomized time; on dense graphs this is O k(n k), and for k=3 it gives an O(nm) -time algorithm. We improve the dense-graph exponent from k to k-1 and obtain the same exponent deterministically. After aggregating parallel edges in O(m) time, our randomized algorithm runs with high probability in k O(k 2)n k-1 2n time, while our deterministic algorithm runs in k O(k 2)n k-1 O(1)n time. In particular, weighted Minimum 3-Cut can be solved in O(n 2 squared n) randomized time and in O(n 2) deterministic time. The algorithms have two main components. First, we give a faster algorithm for weighted Minimum 3-Cut. After handling optima with a very small side and optima with two light sides, the remaining optimum has a unique structured side. Tree packing reduces its completion to a batched collection of 2-respecting cut problems. Second, we reduce Minimum k-Cut to Minimum 3-Cut by enumerating a bounded family of light-cut candidates and recursively completing either side of each candidate. If the enumeration produces too many cuts, then we can instead produce an optimum k-cut directly. We derandomize the 3-cut algorithm using a deterministic near-minimum-cut skeleton, and derandomize the reduction using a specialized 4-cut algorithm using the skeleton, the constructive light-cut bounds, and the deterministic spectral sparsifier of.
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time