Faster Minimum k-Cut I: Simple and Sparse Weighted Graphs

Abstract

The minimum $k$-cut problem asks for the fewest edges whose removal leaves an input graph with at least $k$ connected components. Previously, the best algorithm for simple graphs ran in $O_k(n^{(1-\epsilon )k+O(1)})$ time~\cite{HL22}, showing that the \(n^k\) barrier can be broken up to a polynomial overhead. We give the first ${\tilde{O}}_k(n^{ck})$-time algorithm for Minimum $k$-Cut on simple graphs for an absolute constant $c<1$. More precisely, the running times are $\tilde{O}(n^2)$ for $k=3$, $\tilde{O}(n^{55/19})$ for $k=4$, and $\tilde{O}(n^{4.112007})$ for $k=5$; for every $k\ge 6$, the running time is \[ k^{O(k^2)}n^{1+(6k-6)\frac{k-1.749614}{7k-10}}(\log n)^{O(k^2)}, \] whose exponent is $\frac{6}{7}k-0.132\dots +O(1/k)$. The algorithm combines three ingredients. First, for weighted Minimum $k$-Cut we give a randomized \[ k^{O(k^2)}n^{k-2}(m+n)\log^3(n) \] -time algorithm: it perturbs the edge weights so that any minimum $k$-cut has a side with boundary strictly smaller than average. These then cut few edges of some tree in a logarithmic-size sample from a tree packing with high probability. After we enumerate them, we recursively compute $(k-1)$-cuts to complete them to the $k$-cuts of which they were a part. A variant of the perturbation and processing the entire packing support give a deterministic $k^{O(k^2)}{n}^{k+O(1)}$-time variant. Second, for cut size $s$, we give an improved FPT algorithm using a near-linear-time construction of an $(O(s{\log }^{2}n\log \log n),s)$ edge-unbreakable tree decomposition with $O(s{\log }^{2}n\log \log n)$ adhesion; this also gives a near-linear-time approximation algorithm for Minimum $k$-Cut. Third, we refine the border/island framework of~\cite{HL22}, using rectangular matrix multiplication to recover singleton islands and balancing it against the improved FPT algorithm.