paper

Faster Minimum k-Cut II: Improved Randomized and Deterministic Algorithms for Weighted Graphs

arXiv:2609.27797

Abstract

The Minimum -Cut problem asks for a minimum-weight set of edges whose removal leaves an undirected weighted graph with at least connected components. We consider only . The fastest previous algorithm for weighted graphs ran in randomized time~\cite{LV26}; on dense graphs this is , and for it gives an -time algorithm. We improve the dense-graph exponent from to and obtain the same exponent deterministically. After aggregating parallel edges in time, our randomized algorithm runs with high probability in \begin{equation*} k^{O(k^2)}n^{k-1}\log^2n \end{equation*} time, while our deterministic algorithm runs in \begin{equation*} k^{O(k^2)}n^{k-1}\log^{O(1)}n \end{equation*} time. In particular, weighted Minimum -Cut can be solved in randomized time and in deterministic time. The algorithms have two main components. First, we give a faster algorithm for weighted Minimum -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 -respecting cut problems. Second, we reduce Minimum -Cut to Minimum -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 -cut directly. We derandomize the -cut algorithm using a deterministic near-minimum-cut skeleton, and derandomize the reduction using a specialized -cut algorithm using the skeleton, the constructive light-cut bounds, and the deterministic spectral sparsifier of \cite{BSS12}.