Cluster Deletion is as Hard to Approximate as Vertex Cover

Yixin Cao, Ying Xu

Recent breakthroughs in Cluster Editing have motivated attempts to adapt these approaches to obtain better-than-$2$ approximations for Cluster Deletion. We rule out this possibilit…