Cluster deletion in cographs, permutation graphs, and graphs with bounded clique number

Abstract

The Cluster Deletion problem asks for a minimum-size edge set whose deletion turns a graph into a disjoint union of complete graphs. Equivalently, the Clique Partition problem asks for a partition of the vertex set into cliques that maximizes the number of edges within the parts. We give a simpler proof of a result of Gao, Hare, and Nastos (Discete Mathematics, 2013), that Cluster Deletion is polynomial-time solvable on cographs. In addition, we show that the natural linear programming formulation of Clique Partition is exact on cographs. We then show that Cluster Deletion is NP-complete on permutation graphs, which are a superclass of cographs. This answers an open question of Konstantinidis and Papadopoulos (Algorithmica, 2021). We also exhibit a permutation graph on nine vertices for which the linear programming formulation is not exact. Finally, for graphs with clique number at most $c$, we give a polynomial-time $2\left(\genfrac{}{}{0ex}{}{c}{2}\right)/((\genfrac{}{}{0ex}{}{c}{2})+1)$-approximation algorithm for Clique Partition. More generally, the algorithm runs in polynomial time on every graph class for which a maximum clique can be found in polynomial time. For each fixed $c\ge 3$, we also construct infinitely many examples attaining the stated approximation ratio. The same examples show that, for Cluster Deletion , the algorithm is a $2$-approximation and no better, for every fixed $c\ge 3$.

20 pages, 3 figures. New title and new co-author Arnaud Patey. The main new result is an NP-completeness proof for permutation graphs. The NP-completeness proof was found by Arnaud Patey with the help of ChatGPT 5.6 Sol. The ChatGPT 5.6 Sol proof contained some errors and has been completely rewritten by the authors