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, k ], a (2 – h/k )-approximation algorithm for k -cut that runs in time n O ( h ). Hence to get a (2 – ε )-approximation algorithm for some absolute constant ε, the best runtime using prior techniques is n O ( 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 -C ut 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 -C ut 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 2 O ( κ 6 ) · Õ ( n 4 ). This is the first FPT algorithm that is parameterized only by k and strictly improves the 2-approximation.

Authors

• Anupam Gupta 0001
• Euiwoong Lee
• Jason Li 0006

Keywords

No keywords are indexed for this paper.