Token Jumping in Planar Graphs has Linear Sized Kernels
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929456700981248 |
|---|---|
| author | Cranston, Daniel W. |
| author_facet | Cranston, Daniel W. |
| contents | Let $G$ be a planar graph and $I_s$ and $I_t$ be two independent sets in $G$, each of size $k$. We begin with a "token" on each vertex of $I_s$ and seek to move all tokens to $I_t$, by repeated "token jumping", removing a single token from one vertex and placing it on another vertex. We require that each intermediate arrangement of tokens again specifies an independent set of size $k$. Given $G$, $I_s$, and $I_t$, we ask whether there exists a sequence of token jumps that transforms $I_s$ to $I_t$. When $k$ is part of the input, this problem is known to be PSPACE-complete. However, it was shown by Ito, Kamiński, and Ono to be fixed-parameter tractable. That is, when $k$ is fixed, the problem can be solved in time polynomial in the order of $G$. Here we strengthen the upper bound on the running time in terms of $k$ by showing that the problem has a kernel of size linear in $k$. More precisely, we transform an arbitrary input problem on a planar graph into an equivalent problem on a (planar) graph with order $O(k)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_09543 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Token Jumping in Planar Graphs has Linear Sized Kernels Cranston, Daniel W. Discrete Mathematics Computational Complexity 05C69, 05C10, 05C85 Let $G$ be a planar graph and $I_s$ and $I_t$ be two independent sets in $G$, each of size $k$. We begin with a "token" on each vertex of $I_s$ and seek to move all tokens to $I_t$, by repeated "token jumping", removing a single token from one vertex and placing it on another vertex. We require that each intermediate arrangement of tokens again specifies an independent set of size $k$. Given $G$, $I_s$, and $I_t$, we ask whether there exists a sequence of token jumps that transforms $I_s$ to $I_t$. When $k$ is part of the input, this problem is known to be PSPACE-complete. However, it was shown by Ito, Kamiński, and Ono to be fixed-parameter tractable. That is, when $k$ is fixed, the problem can be solved in time polynomial in the order of $G$. Here we strengthen the upper bound on the running time in terms of $k$ by showing that the problem has a kernel of size linear in $k$. More precisely, we transform an arbitrary input problem on a planar graph into an equivalent problem on a (planar) graph with order $O(k)$. |
| title | Token Jumping in Planar Graphs has Linear Sized Kernels |
| topic | Discrete Mathematics Computational Complexity 05C69, 05C10, 05C85 |
| url | https://arxiv.org/abs/2401.09543 |