Open Access Open Access  Restricted Access Subscription or Fee Access

A constraint programming approach to the cluster editing problem

Amel Mhamdi, Wady Naanaa

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.

Keywords


Cluster editing, Fixed parameter tractability, Cliques partition, Constraint programming, Limited discrepancy search, Algorithm engineering, Computer experiments.

Full Text:

PDF


Disclaimer/Regarding indexing issue:

We have provided the online access of all issues and papers to the indexing agencies (as given on journal web site). It’s depend on indexing agencies when, how and what manner they can index or not. Hence, we like to inform that on the basis of earlier indexing, we can’t predict the today or future indexing policy of third party (i.e. indexing agencies) as they have right to discontinue any journal at any time without prior information to the journal. So, please neither sends any question nor expects any answer from us on the behalf of third party i.e. indexing agencies.Hence, we will not issue any certificate or letter for indexing issue. Our role is just to provide the online access to them. So we do properly this and one can visit indexing agencies website to get the authentic information.