Revised: March 27, 2022

Published: April 19, 2022

**Keywords:**$k$-cut, multiplicative weight updates

**Categories:**algorithms, approximation algorithms, graphs, $k$-cut, multiplicative weight updates, LP relaxation, APPROX, APPROX-RANDOM 2019 special issue

**ACM Classification:**F.2.2, G.1.6

**AMS Classification:**68W25

**Abstract:**
[Plain Text Version]

In an undirected graph, a $k$-cut is a set of edges whose removal breaks the graph into at least $k$ connected components. The minimum-weight $k$-cut can be computed in $n^{O(k)}$ time, but when $k$ is treated as part of the input, computing the minimum-weight $k$-cut is NP-hard [Goldschmidt and Hochbaum 1994]. For poly$({m,n,k})$-time algorithms, the best possible approximation factor is essentially 2 under the Small-Set Expansion Hypothesis [Manurangsi 2017]. Saran and Vazirani [1995] showed that a $(2 - 2/k)$-approximately minimum-weight $k$-cut can be computed via $O(k)$ minimum cuts, which implies a $\tilde{O}(k m)$ randomized running time via the nearly linear-time randomized min-cut algorithm of Karger [2000]. Nagamochi and Kamidoi [2007] showed that a $(2 - 2/k)$-approximately minimum-weight $k$-cut can be computed deterministically in $O(mn + n^2 \log n)$ time. These results prompt two basic questions. The first concerns the role of randomization. Is there a deterministic algorithm for $2$-approximate minimum $k$-cut, matching the randomized running time of $\tilde{O}(k m)$? The second question qualitatively compares minimum cut to 2-approximate minimum $k$-cut. Can $2$-approximate minimum $k$-cut be computed as fast as the minimum cut—in $\tilde{O}(m)$ randomized time?

We give a deterministic approximation algorithm that computes $(2+\epsilon)$-approximate minimum $k$-cut in $O(m \log^3 n / \epsilon^2)$ time, via a $(1+\epsilon)$-approximation for an LP relaxation of $k$-cut.

-------------

An extended abstract of this paper appeared in the Proceedings of the 22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'19).