2026-07-23T06:06:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9945 2024-03-06T10:45:10Z ddc:004 open_access

Parameterized Dynamic Cluster Editing Luo, Junjie Molter, Hendrik Nichterlein, André Niedermeier, Rolf graph-based data clustering goal-oriented clustering compromise clustering NP-hard problems fixed-parameter tractability parameterized hardness We introduce a dynamic version of the NP-hard Cluster Editing problem. 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 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 (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 two open questions) providing a fairly complete picture of the parameterized computational complexity landscape under the perhaps two most natural parameterizations: the distance of the new "similar" cluster graph to (i) the second input graph and to (ii) the input cluster graph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Junjie Luo and Hendrik Molter and André Nichterlein and Rolf Niedermeier 2018 Is Part Of LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2018.46 urn:nbn:de:0030-drops-99450 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.46 eng https://creativecommons.org/licenses/by/3.0/legalcode