Chen, Jiehua ;
Molter, Hendrik ;
Sorge, Manuel ;
Suchý, Ondrej
Cluster Editing in MultiLayer and Temporal Graphs
Abstract
Motivated by the recent rapid growth of research for algorithms to cluster multilayer and temporal graphs, we study extensions of the classical Cluster Editing problem. In MultiLayer Cluster Editing we receive a set of graphs on the same vertex set, called layers and aim to transform all layers into cluster graphs (disjoint unions of cliques) that differ only slightly. More specifically, we want to mark at most d vertices and to transform each layer into a cluster graph using at most k edge additions or deletions per layer so that, if we remove the marked vertices, we obtain the same cluster graph in all layers. In Temporal Cluster Editing we receive a sequence of layers and we want to transform each layer into a cluster graph so that consecutive layers differ only slightly. That is, we want to transform each layer into a cluster graph with at most k edge additions or deletions and to mark a distinct set of d vertices in each layer so that each two consecutive layers are the same after removing the vertices marked in the first of the two layers. We study the combinatorial structure of the two problems via their parameterized complexity with respect to the parameters d and k, among others. Despite the similar definition, the two problems behave quite differently: In particular, MultiLayer Cluster Editing is fixedparameter tractable with running time k^{O(k + d)} s^{O(1)} for inputs of size s, whereas Temporal Cluster Editing is W[1]hard with respect to k even if d = 3.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2018:9972,
author = {Jiehua Chen and Hendrik Molter and Manuel Sorge and Ondrej Such{\'y}},
title = {{Cluster Editing in MultiLayer and Temporal Graphs}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {24:124:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9972},
URN = {urn:nbn:de:0030drops99729},
doi = {10.4230/LIPIcs.ISAAC.2018.24},
annote = {Keywords: Cluster Editing, Temporal Graphs, MultiLayer Graphs, FixedParameter Algorithms, Polynomial Kernels, Parameterized Complexity}
}
06.12.2018
Keywords: 

Cluster Editing, Temporal Graphs, MultiLayer Graphs, FixedParameter Algorithms, Polynomial Kernels, Parameterized Complexity 
Seminar: 

29th International Symposium on Algorithms and Computation (ISAAC 2018)

Issue date: 

2018 
Date of publication: 

06.12.2018 