This paper deals with a variant of the well-known Cluster Editing Problem (CEP), more precisely, the \textit{p}-CEP, in which a given input graph should be edited by adding and/or removing edges in such a way that \textit{p} vertex-disjoint cliques (clusters) are generated with the minimum number of editions. We introduce several valid inequalities where some of them turned out to be very effective when implemented in branch-and-cut approaches over two mathematical formulations. Computational experiments were carried out over a set of instances available in the CEP literature. The results obtained show the efficiency of the approaches according to the value of \textit{p}, the graph density and the ratio between \textit{p} and the number of vertices.
Citation
Working Paper, UFPB