Theory of Computing
-------------------
Title     : Fast and Deterministic Approximations for $k$-Cut
Authors   : Kent Quanrud
Volume    : 18
Number    : 7
Pages     : 1-24
URL       : https://theoryofcomputing.org/articles/v018a007

Abstract
--------

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).