A nearly 5/3-approximation FPT Algorithm for Min-k-Cut
A nearly 5/3-approximation FPT Algorithm for Min-k-Cut
复制标题
一种近 5/3 近似的 Min-k-Cut FPT 算法
DOI：
10.1137/1.9781611975994.59
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Lin Bingkai
中科院分区：
文献类型：
--
作者：
Kawarabayashi Ken-ichi;Lin Bingkai
给定一个边权图G，min-k-cut问题要求一组具有最小总权的边，去除这些边将图G分解为至少k个连通分量。贪婪算法可以在多项式时间内找到min-k-割的（2 - 2/k）-近似。在小集合扩展假设（SSEH）下，没有多项式时间算法能达到比2更好的近似比[9]。最近，Gupta，Lee和Li [5]给出了一个1.9997近似的FPT算法。他们还将近似比提高到1.81 [4]。我们推广了他们的证明技巧，并证明了min-k-cut有一个接近5/3近似的FPT算法。我们的证明是独立的，比古普塔，李和李短得多。
Given an edged-weighted graphG, the min-k-cut problem asks for a set of edges with minimum total weight whose removal breaks the graphGinto at leastkconnected 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 byk. 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.