  The Cluster Editing problem seeks a transformation of a given undirected
graph into a disjoint union of cliques via a minimum number of edge additions
or deletions. A multi-parameterized version of the problem is studied,
featuring a number of input parameters that bound the amount of both
edge-additions and deletions per single vertex, as well as the size of a
clique-cluster. We show that the problem remains NP-hard even when only one
edge can be deleted and at most two edges can be added per vertex. However, the
new formulation allows us to solve Cluster Editing (exactly) in polynomial time
when the number of edge-edit operations per vertex is smaller than half the
minimum cluster size. In other words, Correlation Clustering can be solved
efficiently when the number of false positives/negatives per single data
element is expected to be small compared to the minimum cluster size. As a
byproduct, we obtain a kernelization algorithm that delivers linear-size
kernels when the two edge-edit bounds are small constants.
