Going weighted: Parameterized algorithms for cluster editing

The goal Of the CLUSTER EDITING problem is to make the fewest changes to the edge set of an input graph such that the resulting graph is a disjoint union Of cliques. This problem is NP-complete but recently, several parameterized algorithms have been proposed. In this paper, we present a number of surprisingly simple search tree algorithms for WEIGHTED CLUSTER EDITING assuming that edge insertion and deletion costs are positive integers. We show that the smallest search tree has size O(1.82(k)) for edit cost k, resulting in the currently fastest parameterized algorithm, both for this problem and its unweighted counterpart. We have implemented and compared our algorithms, and achieved promising results.(1) (C) 2009 Elsevier B.V. All rights reserved.