A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915977110749184 |
|---|---|
| author | Jacob, Ashwin Kumar, Arpit Majumdar, Diptapriyo |
| author_facet | Jacob, Ashwin Kumar, Arpit Majumdar, Diptapriyo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_02399 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees Jacob, Ashwin Kumar, Arpit Majumdar, Diptapriyo Data Structures and Algorithms Discrete Mathematics F.2.2 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. |
| title | A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees |
| topic | Data Structures and Algorithms Discrete Mathematics F.2.2 |
| url | https://arxiv.org/abs/2605.02399 |