  Cluster Editing, also known as Correlation Clustering, is a well-studied
graph modification problem. In this problem, one is given a graph and the task
is to perform up to $k$ edge additions or deletions to transform it into a
cluster graph, i.e., a graph consisting of a disjoint union of cliques.
However, in real-world networks, clusters are often overlapping. For example in
social networks, a person might belong to several communities - e.g. those
corresponding to work, school, or neighborhood. Other strong motivations come
from biological network analysis and from language networks. Trying to cluster
words with similar usage in the latter can be confounded by homonyms, that is,
words with multiple meanings like "bat." In this paper, we introduce a new
variant of Cluster Editing whereby a vertex can be split into two or more
vertices. First used in the context of graph drawing, this operation allows a
vertex $v$ to be replaced by two vertices whose combined neighborhood is the
neighborhood of $v$ (and thus $v$ can belong to more than one cluster). We call
the new problem Cluster Editing with Vertex Splitting and we initiate the study
of it. We show that it is NP-complete and fixed-parameter tractable when
parameterized by the total number $k$ of allowed vertex-splitting and
edge-editing operations. In particular, we obtain an $O(2^{9k log k} + n +
m)$-time algorithm and a $6k$-vertex kernel.
