A polynomial kernel for vertex deletion into bipartite permutation graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911744979369984 |
|---|---|
| author | Derbisz, Jan |
| author_facet | Derbisz, Jan |
| contents | A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines $\ell_1$ and $\ell_2$, one on each. A bipartite permutation graph is a permutation graph which is bipartite.
In the the bipartite permutation vertex deletion problem we ask for a given $n$-vertex graph, whether we can remove at most $k$ vertices to obtain a bipartite permutation graph. This problem is NP-complete but it does admit an FPT algorithm parameterized by $k$.
In this paper we study the kernelization of this problem and show that it admits a polynomial kernel with $O(k^{62})$ vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_14005 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A polynomial kernel for vertex deletion into bipartite permutation graphs Derbisz, Jan Data Structures and Algorithms Discrete Mathematics A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines $\ell_1$ and $\ell_2$, one on each. A bipartite permutation graph is a permutation graph which is bipartite. In the the bipartite permutation vertex deletion problem we ask for a given $n$-vertex graph, whether we can remove at most $k$ vertices to obtain a bipartite permutation graph. This problem is NP-complete but it does admit an FPT algorithm parameterized by $k$. In this paper we study the kernelization of this problem and show that it admits a polynomial kernel with $O(k^{62})$ vertices. |
| title | A polynomial kernel for vertex deletion into bipartite permutation graphs |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2111.14005 |