论文标题
群集顶点删除问题的紧密近似算法
A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem
论文作者
论文摘要
我们为群集顶点删除问题提供了第一个$ 2 $ - APPROXIMATION算法。这很紧，因为在小于$ 2 $的任何常数因子内近似问题是UGC hard。我们的算法根据本地比率技术和真双胞胎的管理结合了先前的方法，以及从输入图的任何顶点的距离上以$ 2 $的最大$ 2 $在顶点上的“良好”成本函数的新颖构造。 作为另一个贡献，我们还从多面体的角度研究了群集顶点缺失，在那里我们证明了线性编程弛豫如何近似问题的上限和下限几乎匹配。
We give the first $2$-approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than $2$ is UGC-hard. Our algorithm combines the previous approaches, based on the local ratio technique and the management of true twins, with a novel construction of a 'good' cost function on the vertices at distance at most $2$ from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem.
