License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11896/
Go to the corresponding LIPIcs Volume Portal

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:
LIPIcs-STACS-2020-35.pdf (0.7 MB)

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
Collection: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Issue Date: 2020
Date of publication: 04.03.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI