A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees
For researchers in parameterized complexity, this provides the first polynomial kernel for a deletion problem to a scattered class of graphs, advancing the kernelization theory of such problems.
The paper presents the first non-trivial polynomial kernel for the problem of deleting vertices so that each remaining connected component is a clique or a tree, achieving a kernel of O(k^5) vertices.
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.