View PDF

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, 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 study both problems on permutation graphs, a superclass of cographs, and exhibit counterexamples to several natural greedy approaches. We also exhibit a permutation graph whose unique optimal clique partition interleaves both of the linear orders defining the graph, which rules out a natural class of dynamic programming algorithms.
Finally, for graphs with clique number at most $c$, we give a polynomial-time $2\binom{c}{2}/(\binom{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\geq 3$, we construct infinitely many examples attaining the stated approximation ratio, so the analysis is exact.

Submission history

From: Tony Huynh [view email]
[v1] Thu, 1 May 2025 23:45:07 UTC (154 KB)
[v2] Thu, 25 Sep 2025 08:48:10 UTC (160 KB)
[v3] Mon, 17 Aug 2026 09:00:35 UTC (47 KB)