2-approximation for Cluster Vertex Deletion

2-Approximation Conjecture for Cluster-VD · arXiv:1808.10370

arXiv Informal medium confidence— first stated 2019-02-22

Authors: Samuel Fiorini, Gwenaël Joret, Oliver Schaudt

Status solved high confidence

The conjecture that Cluster-VD admits a 2-approximation in polynomial time was resolved affirmatively by Aprile, Drescher, Fiorini, and Huynh in 2020. Their paper arXiv:2007.08057 presents the first 2-approximation algorithm for the (weighted) cluster vertex deletion problem, matching the UGC-hardness lower bound of 2 established via a reduction from Vertex Cover. The result was published in Mathematical Programming in 2021.

Cited literature (1)

proof A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem (2020)

Manuel Aprile, Matthew Drescher, Samuel Fiorini, Tony Huynh · Mathematical Programming (published 2021) · arXiv:2007.08057 · doi:10.1007/s10107-021-01744-w

Proves the first 2-approximation algorithm for weighted Cluster Vertex Deletion, establishing that the approximation ratio is tight under the Unique Games Conjecture.

Reviewer notes. The conjecture was posed in the source paper (arXiv:1808.10370) and resolved the same year as the journal publication of the source paper. Two of the four authors of the resolving paper (Fiorini and Huynh) are connected to the graph-theory community tracked in the curated corpus. No internal corpus references to this conjecture were supplied.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. Cluster-VD can be 2-approximated in polynomial time.

Context

The authors establish a 9/4-approximation algorithm for the weighted Cluster Vertex Deletion problem (finding a minimum cost vertex set whose deletion leaves no induced $P_3$). Since Cluster-VD is UGC-hard to approximate to within any ratio better than 2 (via a reduction from Vertex Cover), a 2-approximation is the natural target. The authors note their 9/4-approximation already achieves ratio 2 when the largest clique has size at most 4, and can be modified to a 2-approximation on diamond-free graphs, providing partial support for the conjecture.

Notes. Stated in prose in both the abstract and the introduction without a labelled conjecture environment; language is unambiguously conjectural ('We further conjecture that …').

Source paper

Improved approximation algorithms for hitting 3-vertex paths
Samuel Fiorini, Gwenaël Joret, Oliver Schaudt · 2019-02-22
https://arxiv.org/abs/1808.10370 PDF source