A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918510508113920 |
|---|---|
| author | Jacob, Ashwin Majumdar, Diptapriyo Zehavi, Meirav |
| author_facet | Jacob, Ashwin Majumdar, Diptapriyo Zehavi, Meirav |
| contents | The class of graph deletion problems has been extensively studied in theoretical computer science, particularly in the field of parameterized complexity. Recently, a new notion of graph deletion problems was introduced, called deletion to scattered graph classes, where after deletion, each connected component of the graph should belong to at least one of the given graph classes. While fixed-parameter algorithms were given for a wide variety of problems, little progress has been made on the kernelization complexity of any of them. In this paper, we present the first non-trivial polynomial kernel for one such deletion problem, where, after deletion, each connected component should be a clique or a tree - that is, as densest as possible or as sparsest as possible (while being connected). We develop a kernel consisting of O(k^5) vertices for this problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14209 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees Jacob, Ashwin Majumdar, Diptapriyo Zehavi, Meirav Data Structures and Algorithms Discrete Mathematics G.2.2 The class of graph deletion problems has been extensively studied in theoretical computer science, particularly in the field of parameterized complexity. Recently, a new notion of graph deletion problems was introduced, called deletion to scattered graph classes, where after deletion, each connected component of the graph should belong to at least one of the given graph classes. While fixed-parameter algorithms were given for a wide variety of problems, little progress has been made on the kernelization complexity of any of them. In this paper, we present the first non-trivial polynomial kernel for one such deletion problem, where, after deletion, each connected component should be a clique or a tree - that is, as densest as possible or as sparsest as possible (while being connected). We develop a kernel consisting of O(k^5) vertices for this problem. |
| title | A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees |
| topic | Data Structures and Algorithms Discrete Mathematics G.2.2 |
| url | https://arxiv.org/abs/2409.14209 |