A nearly 5/3-approximation FPT Algorithm for Min-k-Cut
Ken‐ichi Kawarabayashi, Bingkai Lin · Society for Industrial and Applied Mathematics eBooks · 2019
Given an edged-weighted graph G, the min-k-cut problem asks for a set of edges with minimum total weight whose removal breaks the graph G into at least k connected components. It is well-known that the greedy algorithm can find a (2 – 2/k)-approximation of the min-k-cut in polynomial time. Assuming the Small Set Expansion Hypothesis (SSEH), no polynomial time algorithm can achieve an approximation ratio better than two [9]. Recently, Gupta, Lee and Li [5] gave a 1.9997-approximation FPT algorithm for the min-k-cut parameterized by k. They also improved this approximation ratio to 1.81 [4]. We generalize their proof techniques and show that the min-k-cut has a nearly 5/3-approximation FPT algorithm. Our proof is self-contained and much shorter than that of Gupta, Lee and Li.