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

Preprint · Jason Li, Trevor Vaughn

- Archive id: arxiv:2609.27781
- Published: 2026-08-17
- arXiv: https://arxiv.org/abs/2609.27781
- Source URL: https://arxiv.org/abs/2609.27781
- PDF: https://arxiv.org/pdf/2609.27781
- Provenance: arxiv

## 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-\\varepsilon)k+O(1)})$ time~\\cite{HL22}, showing that the \\(n^k\\) barrier can be broken up to a polynomial overhead. We give the first $\\widetilde 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 $\\widetilde O(n^2)$ for $k=3$, $\\widetilde O(n^{55/19})$ for $k=4$, and $\\widetilde O(n^{4.112007})$ for $k=5$; for every $k\\ge6$, 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 $\\frac67k-0.132\\ldots+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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.