Exact and Heuristic Solution Approaches for the Cluster Deletion Problem on General Graphs

A cluster graph is a disjoint union of cliques, obtained by clustering the nodes of a given network and then removing the edges between nodes assigned to different clusters. The Cluster Deletion problem asks for the smallest subset of edges to be removed from a network in order to produce a cluster graph, which is equivalent to determining the largest subset of edges to be preserved. The problem finds application in many fields, including computational biology, bioinformatics, and wireless sensor networks, and it is known to be NP$$ \mathrm{NP} $$-hard on general graphs. In this work, we formulate the problem as an integer linear program, and we devise a heuristic approach based on edge contraction operations. We test the proposed approaches on both artificial instances and benchmark biological networks.