[Zurück]

S. Li, M. Pilipczuk, M. Sorge:
"Cluster Editing Parameterized Above Modification-Disjoint P3-Packings";
Vortrag: Symposium on Theoretical Aspects of Computer Science (STACS), Saarbrücken (Germany); 16.03.2021 - 19.03.2021; in: "38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)", LIPICS, 187 (2021), ISBN: 978-3-95977-180-1; S. 1 - 16.

transform G into a union of vertex-disjoint 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 H of modification-disjoint induced P3s (no pair of P3s in H share an
edge or non-edge) and an integer ℓ. The task is to decide whether G can be transformed into a
union of vertex-disjoint cliques by at most ℓ + |H| modifications (edge deletions or insertions). We
show that this problem is NP-hard 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 P3s 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 P3s. Van Bevern et al. showed that the case c = 1 is fixed-parameter tractable with respect
to ℓ and we show that the case c = 2 is solvable in |V |2ℓ+O(1) time.

http://dx.doi.org/10.4230/LIPIcs.STACS.2021.49

https://publik.tuwien.ac.at/files/publik_300335.pdf