A tight approximation algorithm for the cluster vertex deletion problem

• 成果类型: Article
• 署名作者: Aprile, Manuel; Drescher, Matthew; Fiorini, Samuel; Huynh, Tony
• 署名单位: University of Padua; Universite Libre de Bruxelles; Monash University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01744-w
• 发表日期: 2023
• 页码: 1069-1091
• 关键词: relaxations

摘要

We give the first 2-approximation algorithm for the cluster vertex deletion problem. This approximation factor is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines previous approaches, based on the local ratio technique and the management of 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.