2017/10/23 by Gupta, Anupam, Lee, Euiwoong, Li, Jason
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1710.08488
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 (2 - ε)-approximation algorithm that runs in time 2O(k6) ⋅ \widetildeO (n4). This is the first FPT algorithm that is parameterized only by k and strictly improves the 2-approximation.