Sufficient conditions for edit-optimal clusters

•We give local conditions for clusters in optimal Cluster Editing solutions.•Bounded edit degrees is one of the sufficient conditions.•An optimality condition for Cluster Deletion is based on degree sequences.

Cluster Editing is the problem of turning a graph into a cluster graph, that is, a disjoint union of cliques, by a minimum number of edge edits. Cluster Deletion is similarly defined, with edge deletions only. We propose a local notion of edit-optimality: Informally, we say that a crown (a certain type of labeled graph) is edit-optimal if it yields a cluster in some optimal solution to Cluster Editing, in every graph containing this crown as a subgraph. Then we give sufficient conditions for edit-optimality, e.g., in terms of vertex degrees. A condition for Cluster Deletion applies a theorem of Landau (1953) [7] on degree sequences of tournaments. The conditions are particularly suited for planted models of clusterings, and for networks that only partially exhibit a clear cluster structure.