Luo, JunjieMolter, HendrikNichterlein, AndréNiedermeier, Rolf2021-03-152021-03-152020-07-250178-4617https://depositonce.tu-berlin.de/handle/11303/12837http://dx.doi.org/10.14279/depositonce-11637We introduce a dynamic version of the NP -hard graph modification 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) constituting a solution for a first input graph, can we cost-efficiently transform it into a “similar” cluster graph that is a solution for a 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 (three modification scenarios 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 distances of the new “similar” cluster graph to (1) the second input graph and to (2) the input cluster graph.en004 Datenverarbeitung; Informatikcompromise clusteringcorrelation clusteringfixed-parameter tractabilitygoal-oriented clusteringgraph-based data clusteringkernelizationlocal searchmulti-choice knapsackNP-hard problemsparameterized complexityArticle1432-0541