  In the $k$-cut problem, we are given an edge-weighted graph $G$ and an
integer $k$, and have to remove a set of edges with minimum total weight so
that $G$ has at least $k$ connected components. The current best algorithms are
an $O(n^{(2-o(1))k})$ randomized algorithm due to Karger and Stein, and an
$\smash{\tilde{O}}(n^{2k})$ deterministic algorithm due to Thorup. Moreover,
several $2$-approximation algorithms are known for the problem (due to Saran
and Vazirani, Naor and Rabani, and Ravi and Sinha).
  It has remained an open problem to (a) improve the runtime of exact
algorithms, and (b) to get better approximation algorithms. In this paper we
show an $O(k^{O(k)} \, n^{(2\omega/3 + o(1))k})$-time algorithm for $k$-cut.
Moreover, we show an $(1+\epsilon)$-approximation algorithm that runs in time
$O((k/\epsilon)^{O(k)} \,n^{k + O(1)})$, and a $1.81$-approximation in
fixed-parameter time $O(2^{O(k^2)}\,\text{poly}(n))$.
