  In the Min $k$-Cut problem, input is an edge weighted graph $G$ and an
integer $k$, and the task is to partition the vertex set into $k$ non-empty
sets, such that the total weight of the edges with endpoints in different parts
is minimized. When $k$ is part of the input, the problem is NP-complete and
hard to approximate within any factor less than $2$. Recently, the problem has
received significant attention from the perspective of parameterized
approximation. Gupta et al.~[SODA 2018] initiated the study of
FPT-approximation for the Min $k$-Cut problem and gave an
$1.9997$-approximation algorithm running in time
$2^{\mathcal{O}(k^6)}n^{\mathcal{O}(1)}$. Later, the same set of authors~[FOCS
2018] designed an $(1 +\epsilon)$-approximation algorithm that runs in time
$(k/\epsilon)^{\mathcal{O}(k)}n^{k+\mathcal{O}(1)}$, and a $1.81$-approximation
algorithm running in time $2^{\mathcal{O}(k^2)}n^{\mathcal{O}(1)}$. More,
recently, Kawarabayashi and Lin~[SODA 2020] gave a $(5/3 +
\epsilon)$-approximation for Min $k$-Cut running in time $2^{\mathcal{O}(k^2
\log k)}n^{\mathcal{O}(1)}$.
  In this paper we give a parameterized approximation algorithm with best
possible approximation guarantee, and best possible running time dependence on
said guarantee (up to Exponential Time Hypothesis (ETH) and constants in the
exponent). In particular, for every $\epsilon > 0$, the algorithm obtains a $(1
+\epsilon)$-approximate solution in time
$(k/\epsilon)^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$. The main ingredients of our
algorithm are: a simple sparsification procedure, a new polynomial time
algorithm for decomposing a graph into highly connected parts, and a new exact
algorithm with running time $s^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ on
unweighted (multi-) graphs. Here, $s$ denotes the number of edges in a minimum
$k$-cut. The latter two are of independent interest.
