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.

翻译：我们给出了组群顶部删除问题的首个$$( $$- 接近 ) 算法。 这是紧凑的, 因为在小于$2美元的任何恒定因子中, 问题近似于 UGC-hard 。 我们的算法结合了以前的做法, 以本地比率技术和真正的双胞胎管理为基础, 在输入图的任何顶端的远端的顶端新建了“ 好”成本函数, 最多为$2 美元。 作为额外贡献, 我们还研究组顶部从综合角度删除, 在那里,我们几乎可以匹配线性编程松动如何接近问题的上下限 。