A tight approximation algorithm for the cluster vertex deletion problem

Manuel Aprile, Matthew Drescher, Samuel Fiorini, Tony Huynh

Research output: Contribution to journalArticleResearchpeer-review

10 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)1069-1091
Number of pages23
JournalMathematical Programming
Volume197
Issue number2
DOIs
Publication statusPublished - Feb 2023

Keywords

  • Approximation algorithm
  • Cluster vertex deletion
  • Linear programming relaxation
  • Sherali-Adams hierarchy

Cite this