TY - JOUR
T1 - A tight approximation algorithm for the cluster vertex deletion problem
AU - Aprile, Manuel
AU - Drescher, Matthew
AU - Fiorini, Samuel
AU - Huynh, Tony
N1 - Funding Information:
This project was supported by ERC Consolidator Grant 615640-ForEFront. Samuel Fiorini and Manuel Aprile are also supported by FNRS grant T008720F-35293308-BD-OCP. Tony Huynh is also supported by the Australian Research Council.
Publisher Copyright:
© 2021, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.
PY - 2023/2
Y1 - 2023/2
N2 - 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.
AB - 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.
KW - Approximation algorithm
KW - Cluster vertex deletion
KW - Linear programming relaxation
KW - Sherali-Adams hierarchy
UR - http://www.scopus.com/inward/record.url?scp=85122367042&partnerID=8YFLogxK
U2 - 10.1007/s10107-021-01744-w
DO - 10.1007/s10107-021-01744-w
M3 - Article
AN - SCOPUS:85122367042
SN - 0025-5610
VL - 197
SP - 1069
EP - 1091
JO - Mathematical Programming
JF - Mathematical Programming
IS - 2
ER -