  We introduce a dynamic version of the NP-hard graph problem Cluster Editing.
The essential point here is to take into account dynamically evolving input
graphs: Having a cluster graph (that is, a disjoint union of cliques) that
represents a solution for the first input graph, can we cost-efficiently
transform it into a "similar" cluster graph that is a solution for the second
("subsequent") input graph? This model is motivated by several application
scenarios, including incremental clustering, the search for compromise
clusterings, or also local search in graph-based data clustering. We thoroughly
study six problem variants (edge editing, edge deletion, edge insertion; each
combined with two distance measures between cluster graphs). We obtain both
fixed-parameter tractability as well as (parameterized) hardness results, thus
(except for three open questions) providing a fairly complete picture of the
parameterized computational complexity landscape under the two perhaps most
natural parameterizations: the distance of the new "similar" cluster graph to
(i) the second input graph and to (ii) the input cluster graph.
