A constraint programming approach to the cluster editing problem

Abstract

Given a simple graph G = (V;E), the problem dealt with in this paper consists in partitioning V into a disjoint union of cliques by adding or removing a minimum number of edges. The problem, which is refered to by Cluster Editing, is NP-hard in general. Solving Cluster Editing is a very time-consuming task. This observation has motivated our investigation of improving the chance for finding a disjoint union of cliques in a limited amount of search. To this end, we formulate the problem in terms of a Weighted Constraint Satisfaction Problem (WCSP), a widely used framework for solving hard combinatorial problems. As search strategy, we apply a Limited Discrepancy Search coupled with a branch-and-bound algorithm, a combination which has proved to be very advantageous. We theoretically and exprimentally show that the proposed approach outperforms the most used algorithm in solving cluster editing, namely, fixed parameter tractable algorithms. The comparison clearly show that our approach is very competitive, especially on large cluster editing instances.