Applied Bioinformatics Group

A   A   A
Home > Publications > Exact Algorithms for Cluster Editing: Evaluation and Experiments

Skip to content. | Skip to navigation

Sebastian Böcker, Sebastian Briesemeister, and Gunnar W Klau (2011)

Exact Algorithms for Cluster Editing: Evaluation and Experiments

Algorithmica, 60(2):316-334.

The Cluster Editing problem is defi ned as follows: Given an undirected, loopless graph, we want to find a set of edge modi cations (insertions and deletions) of minimum cardinality, such that the modi ed graph consists of disjoint cliques. We present empirical results for this problem using exact methods from fixed-parameter algorithmics and linear programming. We investigate parameter-independent data reduction methods and fi nd that e ffective preprocessing is possible if the number of edge modi cations k is smaller than some multiple of |V|, where V is the vertex set of the input graph. In particular, combining parameter-dependent data reduction with lower and upper bounds we can e ffectively reduce graphs satisfying k <= 25|V|. In addition to the fastest known fi xed-parameter branching strategy for the problem, we investigate an integer linear program (ILP) formulation of the problem using a cutting plane approach. Our results indicate that both approaches are capable of solving large graphs with 1000 vertices and several thousand edge modi cations. For the fi rst time, complex and very large graphs such as biological instances allow for an exact solution, using a combination of the above techniques.
A preliminary version of this paper appeared under the title 'Exact algorithms for cluster editing: Evaluation and experiments' in the Proceedings of the 7th Workshop on Experimental Algorithms, WEA 2008, in: LNCS, vol. 5038, Springer, pp. 289-302
Printable file