Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2018.46
URN: urn:nbn:de:0030-drops-99450
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9945/
Luo, Junjie ; Molter, Hendrik ; Nichterlein, André ; Niedermeier, Rolf
Parameterized Dynamic Cluster Editing
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{luo_et_al:LIPIcs:2018:9945,
author = {Junjie Luo and Hendrik Molter and Andr{\'e} Nichterlein and Rolf Niedermeier},
title = {{Parameterized Dynamic Cluster Editing}},
booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
pages = {46:1--46:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-093-4},
ISSN = {1868-8969},
year = {2018},
volume = {122},
editor = {Sumit Ganguly and Paritosh Pandya},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9945},
URN = {urn:nbn:de:0030-drops-99450},
doi = {10.4230/LIPIcs.FSTTCS.2018.46},
annote = {Keywords: graph-based data clustering, goal-oriented clustering, compromise clustering, NP-hard problems, fixed-parameter tractability, parameterized hardness}
}
| Keywords: | graph-based data clustering, goal-oriented clustering, compromise clustering, NP-hard problems, fixed-parameter tractability, parameterized hardness | |
| Seminar: | 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 05.12.2018 |
