Given a simple graph G=(V,E), the problem dealt with in this paper ask to transform a graph G by, only removing a minimum number of edges, into a disjoint union of cliques. This optimization problem is known to be NP-hard and is referred to as the Cluster Deletion problem (CD). This observation has motivated us to improve the chance for finding a disjoint union of cliques in a limited amount of search. To this end, we propose an encoding of CD in terms of a Weighted Constraint Satisfaction Problem (WCSP), a framework which has been widely used in solving hard combinatorial problems.

We compare our approach with a fixed-parameter tractability FPT algorithm, which is one of the most used algorithm for solving the Cluster Deletion problem. Then, we experimentally show that the best results are obtained using the new encoding. We report a comparison of the quality and running times of WCSP and FPT algorithms on both random graphs and protein similarity graphs derived from the COG dataset.