A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees

Abstract

Vertex deletion to hereditary graph class is well-studied in parameterized complexity. Vertex deletion to the scattered graph classes has gained attention in recent years. In this paper, we consider (Proper-Interval, Tree)-Vertex Deletion, the input to which is an undirected graph $G=(V,E)$ and an integer $k$. The goal is to pick a set $X\subseteq V(G)$ of at most $k$ vertices such that $G-X$ is a simple graph and every connected component of $G-X$ is a proper interval graph or a tree. When parameterized by the solution size $k$, (Proper-Interval, Tree)-Vertex Deletion has been proved to be fixed-parameter tractable by Jacob et al. [JCSS-2023, FCT-2021]. In this paper, we consider this problem from the perspective of polynomial kernelization. We provide a first nontrivial polynomial kernel for (Proper-Interval, Tree)-Vertex Deletion, with $O(k^{33})$ vertices.

42 pages, 5 figures