An FPT algorithm beating 2-approximation for k-cut

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 2 [2; k], a (2-ϵ/k)-approximation algorithm for k-cut that runs in time nO(h). Hence to get a (2-ϵ)-approximation algorithm for some absolute constant ", the best runtime using prior techniques is nO(k"). Moreover, it was recently shown that getting a (2-ϵ)-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: 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 " > 0, there exists a (2-ϵ)-approximation algorithm that runs in time 2O(k6) O (n4). This is the first FPT algorithm that is parameterized only by k and strictly improves the 2-approximation.