2026-08-02T02:13:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22168 2024-12-04T06:53:44Z ddc:004 open_access

A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees Jacob, Ashwin Majumdar, Diptapriyo Zehavi, Meirav Parameterized Complexity Kernelization Scattered Graph Classes New Expansion Lemma Cliques or Trees Vertex Deletion 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. Here, 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 dense as possible or as sparse as possible (while being connected). We develop a kernel of O(k⁵) vertices for the same. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ashwin Jacob and Diptapriyo Majumdar and Meirav Zehavi 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.41 urn:nbn:de:0030-drops-221687 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.41 eng https://creativecommons.org/licenses/by/4.0/legalcode