  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 $O(n^{O(k)})$ time, but when $k$ is treated as part of the input,
computing the minimum weight $k$-cut is NP-Hard [Holdschmidt and Hochbaum
1994]. For $\operatorname{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 by $O(k)$ minimum
cuts, which implies an $\tilde{O}(mk)$ randomized running time via the nearly
linear time randomized min-cut algorithm of Karger [2000]. Nagamochi and
Kamidoi [2007] showed that the 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 $k$-cuts matching the randomized
running time of $\tilde{O}(mk)$? The second question qualitatively compares
minimum cut to 2-approximate minimum $k$-cut. Can 2-approximate $k$-cuts be
computed as fast as the (exact) minimum cut - in $\tilde{O}(m)$ randomized
time?
  We make progress on these questions with a deterministic approximation
algorithm that computes $(2 + \epsilon)$-minimum $k$-cuts in $O(m \log^3(n) /
\epsilon^2)$ time, via a $(1 + \epsilon)$-approximate for an LP relaxation of
$k$-cut.
