An FPT Algorithm Beating 2-Approximation for k-Cut
Anupam Gupta, Euiwoong Lee, Jason Li · Society for Industrial and Applied Mathematics eBooks · 2018
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, k], a (2 – h/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 (– ε)-approximation algorithm that runs in time 2O(κ6) · Õ(n4). This is the first FPT algorithm that is parameterized only by k and strictly improves the 2-approximation.