LIPIcs.STACS.2021.49.pdf (1.04 MB)

# Cluster Editing Parameterized above Modification-disjoint P3-packings

journal contribution

posted on 2024-02-19, 09:34 authored by Shaohua LiShaohua Li, Marcin Pilipczuk, Manuel SorgeGiven a graph G =(V,E) and an integer k, the Cluster Editing problem asks whether we can 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 ℋ of modification-disjoint induced P3s (no pair of P3s in ℋ 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 ℓ +|ℋ| 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 ℋ) 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. Here packed P3s are those belonging to the packing ℋ. 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.

## History

## Primary Research Area

- Algorithmic Foundations and Cryptography

## Journal

ACM Transactions on Algorithms## Volume

20## Page Range

1-43## Publisher

Association for Computing Machinery (ACM)## Open Access Type

- Hybrid

## Sub Type

- Article

## BibTeX

@article{Li:Pilipczuk:Sorge:2024, title = "Cluster Editing Parameterized above Modification-disjoint P3-packings", author = "Li, Shaohua" AND "Pilipczuk, Marcin" AND "Sorge, Manuel", year = 2024, month = 1, journal = "ACM Transactions on Algorithms", number = "1", pages = "1--43", publisher = "Association for Computing Machinery (ACM)", issn = "1549-6325", doi = "10.1145/3626526" }## Usage metrics

## Categories

No categories selected## Keywords

Algorithmic Foundations and Cryptography49 Mathematical Sciences4901 Applied Mathematics4904 Pure MathematicsAlgorithmic Foundations and Cryptography RA10103 Numerical and Computational Mathematics0802 Computation Theory and MathematicsComputation Theory & Mathematics4605 Data management and data science4613 Theory of computation

## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC