Title: An FPT Algorithm Beating 2-Approximation for $k$-Cut,
Abstract: 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. Prior work on this problem
gives, for all $h \in [2,k]$, a $(2-h/k)$-approximation algorithm for $k$-cut
that runs in time $n^{O(h)}$. Hence to get a $(2 - \varepsilon)$-approximation
algorithm for some absolute constant $\varepsilon$, the best runtime using
prior techniques is $n^{O(k\varepsilon)}$. Moreover, it was recently shown that
getting a $(2 - \varepsilon)$-approximation for general $k$ is NP-hard,
assuming the Small Set Expansion Hypothesis.
If we use the size of the cut as the parameter, an FPT algorithm to find the
exact $k$-Cut is known, but solving the $k$-Cut problem exactly is $W[1]$-hard
if we parameterize only by the natural parameter of $k$. An immediate question
is: \emph{can we approximate $k$-Cut better in FPT-time, using $k$ as the
parameter?}
We answer this question positively. We show that for some absolute constant
$\varepsilon > 0$, there exists a $(2 - \varepsilon)$-approximation algorithm
that runs in time $2^{O(k^6)} \cdot \widetilde{O} (n^4)$. This is the first FPT
algorithm that is parameterized only by $k$ and strictly improves the
$2$-approximation.