Distance Recoloring
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918504636088320 |
|---|---|
| author | Banerjee, Niranka Engels, Christian Hoang, Duc A. |
| author_facet | Banerjee, Niranka Engels, Christian Hoang, Duc A. |
| contents | Reconfiguration problems ask whether one feasible solution can be transformed into another by a sequence of local moves while maintaining feasibility throughout. For integers $d \geq 1$ and $k \geq d+1$, the Distance Coloring problem asks if a given graph $G$ has a $(d, k)$-coloring, i.e., a coloring of the vertices of $G$ by $k$ colors such that any two vertices within distance $d$ from each other have different colors.
For ordinary proper colorings ($d=1$), the $k$-Coloring Reconfiguration problem is polynomial-time solvable for $k\le 3$ [Cereceda, van den Heuvel, and Johnson, J. Graph Theory 67(1):69--82, 2011] but is $\mathsf{PSPACE}$-complete for every fixed $k\ge 4$, even on bipartite graphs [Bonsma and Cereceda, Theor. Comput. Sci. 410(50):5215--5226, 2009]. In this work, we initiate a study of the distance-$d$ analogue, for $d \geq 2$. We show that even for planar, bipartite, and $2$-degenerate graphs, $(d, k)$-Coloring Reconfiguration remains $\mathsf{PSPACE}$-complete for every $d \geq 3$ via a reduction from the well-known Sliding Tokens problem. Our construction uses $k = k_0 + 2 + n(\lceil d/2\rceil-1)$ colors on instances of size $n$, where $k_0\in\{3d+3,3d+6\}$ (depending on the parity of $d$). For $d = 2$, the same reduction scheme can be adapted to show that the problem is $\mathsf{PSPACE}$-complete on planar and $2$-degenerate graphs with same values of $k$. Additionally, on split graphs, there is an interesting dichotomy: the problem is $\mathsf{PSPACE}$-complete when $d = 2$ and $k$ is large but can be solved efficiently when $d \geq 3$ and $k \geq d+1$. For chordal graphs, we show that the problem is $\mathsf{PSPACE}$-complete for even values of $d \geq 2$. Finally, we design a quadratic-time algorithm to solve the problem on paths for any $d \geq 2$ and $k \geq d+1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_12705 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distance Recoloring Banerjee, Niranka Engels, Christian Hoang, Duc A. Data Structures and Algorithms Discrete Mathematics Reconfiguration problems ask whether one feasible solution can be transformed into another by a sequence of local moves while maintaining feasibility throughout. For integers $d \geq 1$ and $k \geq d+1$, the Distance Coloring problem asks if a given graph $G$ has a $(d, k)$-coloring, i.e., a coloring of the vertices of $G$ by $k$ colors such that any two vertices within distance $d$ from each other have different colors. For ordinary proper colorings ($d=1$), the $k$-Coloring Reconfiguration problem is polynomial-time solvable for $k\le 3$ [Cereceda, van den Heuvel, and Johnson, J. Graph Theory 67(1):69--82, 2011] but is $\mathsf{PSPACE}$-complete for every fixed $k\ge 4$, even on bipartite graphs [Bonsma and Cereceda, Theor. Comput. Sci. 410(50):5215--5226, 2009]. In this work, we initiate a study of the distance-$d$ analogue, for $d \geq 2$. We show that even for planar, bipartite, and $2$-degenerate graphs, $(d, k)$-Coloring Reconfiguration remains $\mathsf{PSPACE}$-complete for every $d \geq 3$ via a reduction from the well-known Sliding Tokens problem. Our construction uses $k = k_0 + 2 + n(\lceil d/2\rceil-1)$ colors on instances of size $n$, where $k_0\in\{3d+3,3d+6\}$ (depending on the parity of $d$). For $d = 2$, the same reduction scheme can be adapted to show that the problem is $\mathsf{PSPACE}$-complete on planar and $2$-degenerate graphs with same values of $k$. Additionally, on split graphs, there is an interesting dichotomy: the problem is $\mathsf{PSPACE}$-complete when $d = 2$ and $k$ is large but can be solved efficiently when $d \geq 3$ and $k \geq d+1$. For chordal graphs, we show that the problem is $\mathsf{PSPACE}$-complete for even values of $d \geq 2$. Finally, we design a quadratic-time algorithm to solve the problem on paths for any $d \geq 2$ and $k \geq d+1$. |
| title | Distance Recoloring |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2402.12705 |