Cluster Editing with Diamond-free Vertices

The Cluster Editing problem asks to transform a graph into a union of disjoint cliques in the minimum number of edge additions and deletions. The Cluster Deletion problem has the same goal, but allows edge deletions only. Recently, a connection between Cluster Editing on diamond-free graphs and Cluster Deletion was established. In this paper we...