A Polynomial Kernel for Proper Helly Circular-arc Vertex Deletion
| Autor: | Agrawal, Akanksha, Jana, Satyabrata, Sahu, Abhishek |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | A proper Helly circular-arc graph is an intersection graph of a set of arcs on a circle such that none of the arcs properly contains any other arc and every set of pairwise intersecting arcs has a common intersection. The Proper Helly Circular-arc Vertex Deletion problem takes as input a graph $G$ and an integer $k$, and the goal is to check if we can remove at most $k$ vertices from the graph to obtain a proper Helly circular-arc graph; the parameter is $k$. Recently, Cao et al.~[MFCS 2023] obtained an FPT algorithm for this (and related) problem. In this work, we obtain a polynomial kernel for the problem. Comment: 25 pages, 3 figures, In LATIN 2024 |
| Databáze: | arXiv |
| Externí odkaz: |
|