Abstract
Given a graph G = (V,E) and an integer k, the Cluster Editing problem asks whether we can transform G into a union of vertexdisjoint cliques by at most k modifications (edge deletions or insertions). In this paper, we study the following variant of Cluster Editing. We are given a graph G = (V,E), a packing ℋ of modificationdisjoint induced P₃s (no pair of P₃s in H share an edge or nonedge) and an integer ?. The task is to decide whether G can be transformed into a union of vertexdisjoint cliques by at most ?+H modifications (edge deletions or insertions). We show that this problem is NPhard even when ? = 0 (in which case the problem asks to turn G into a disjoint union of cliques by performing exactly one edge deletion or insertion per element of H) and when each vertex is in at most 23 P₃s of the packing. This answers negatively a question of van Bevern, Froese, and Komusiewicz (CSR 2016, ToCS 2018), repeated by C. Komusiewicz at Shonan meeting no. 144 in March 2019. We then initiate the study to find the largest integer c such that the problem remains tractable when restricting to packings such that each vertex is in at most c packed P₃s. Van Bevern et al. showed that the case c = 1 is fixedparameter tractable with respect to ? and we show that the case c = 2 is solvable in V^{2? + O(1)} time.
BibTeX  Entry
@InProceedings{li_et_al:LIPIcs.STACS.2021.49,
author = {Li, Shaohua and Pilipczuk, Marcin and Sorge, Manuel},
title = {{Cluster Editing Parameterized Above ModificationDisjoint P₃Packings}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {49:149:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771801},
ISSN = {18688969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13694},
URN = {urn:nbn:de:0030drops136945},
doi = {10.4230/LIPIcs.STACS.2021.49},
annote = {Keywords: Graph algorithms, fixedparameter tractability, parameterized complexity}
}
Keywords: 

Graph algorithms, fixedparameter tractability, parameterized complexity 
Collection: 

38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) 
Issue Date: 

2021 
Date of publication: 

10.03.2021 