Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.35
URN: urn:nbn:de:0030-drops-118961
URL: https://drops.dagstuhl.de/opus/volltexte/2020/11896/
Bonamy, Marthe ; Heinrich, Marc ; Ito, Takehiro ; Kobayashi, Yusuke ; Mizuta, Haruka ; Mühlenthaler, Moritz ; Suzuki, Akira ; Wasa, Kunihiro
Shortest Reconfiguration of Colorings Under Kempe Changes
| pdf-format: |
|
Abstract
A k-coloring of a graph maps each vertex of the graph to a color in {1, 2, …, k}, such that no two adjacent vertices receive the same color. Given a k-coloring of a graph, a Kempe change produces a new k-coloring by swapping the colors in a bicolored connected component. We investigate the complexity of finding the smallest number of Kempe changes needed to transform a given k-coloring into another given k-coloring. We show that this problem admits a polynomial-time dynamic programming algorithm on path graphs, which turns out to be highly non-trivial. Furthermore, the problem is NP-hard even on star graphs and we show that on such graphs it admits a constant-factor approximation algorithm and is fixed-parameter tractable when parameterized by the number k of colors. The hardness result as well as the algorithmic results are based on the notion of a canonical transformation.
BibTeX - Entry
@InProceedings{bonamy_et_al:LIPIcs:2020:11896,
author = {Marthe Bonamy and Marc Heinrich and Takehiro Ito and Yusuke Kobayashi and Haruka Mizuta and Moritz M{\"u}hlenthaler and Akira Suzuki and Kunihiro Wasa},
title = {{Shortest Reconfiguration of Colorings Under Kempe Changes}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {35:1--35:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-140-5},
ISSN = {1868-8969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11896},
URN = {urn:nbn:de:0030-drops-118961},
doi = {10.4230/LIPIcs.STACS.2020.35},
annote = {Keywords: Combinatorial Reconfiguration, Graph Algorithms, Graph Coloring, Kempe Equivalence}
}
| Keywords: | Combinatorial Reconfiguration, Graph Algorithms, Graph Coloring, Kempe Equivalence | |
| Seminar: | 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 04.03.2020 |
