In this paper, we study the cluster editing problem which is fixed parameter tractable. We present the first practical implementation of a FPT based method for cluster editing, using the approach in [6,7], and compare our implementation with the straightforward greedy method and a solution based on linear programming [3]. Our experiments show that the best results are obtained by using the refined branching method in [7] together with interleaving (re-kernelization). We also observe an interesting lack of monotonicity in the running times for "yes" instances with increasing values of k.

School of Computer Science

Dehne, F, Langston, M.A. (Michael A.), Luo, X. (Xuemei), Pitre, S, Shaw, P. (Peter), & Zhang, Y. (Yun). (2006). The cluster editing problem: Implementations and experiments.