Osawa, Hiroki ;
Suzuki, Akira ;
Ito, Takehiro ;
Zhou, Xiao
Algorithms for Coloring Reconfiguration Under Recolorability Constraints
Abstract
Coloring reconfiguration is one of the most wellstudied reconfiguration problems. In the problem, we are given two (vertex)colorings of a graph using at most k colors, and asked to determine whether there exists a transformation between them by recoloring only a single vertex at a time, while maintaining a kcoloring throughout. It is known that this problem is solvable in linear time for any graph if k <=3, while is PSPACEcomplete for a fixed k >= 4. In this paper, we further investigate the problem from the viewpoint of recolorability constraints, which forbid some pairs of colors to be recolored directly. More specifically, the recolorability constraint is given in terms of an undirected graph R such that each node in R corresponds to a color, and each edge in R represents a pair of colors that can be recolored directly. In this paper, we give a lineartime algorithm to solve the problem under such a recolorability constraint if R is of maximum degree at most two. In addition, we show that the minimum number of recoloring steps required for a desired transformation can be computed in linear time for a yesinstance. We note that our results generalize the known positive ones for coloring reconfiguration.
BibTeX  Entry
@InProceedings{osawa_et_al:LIPIcs:2018:9985,
author = {Hiroki Osawa and Akira Suzuki and Takehiro Ito and Xiao Zhou},
title = {{Algorithms for Coloring Reconfiguration Under Recolorability Constraints}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {37:137:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9985},
URN = {urn:nbn:de:0030drops99850},
doi = {10.4230/LIPIcs.ISAAC.2018.37},
annote = {Keywords: combinatorial reconfiguration, graph algorithm, graph coloring}
}
06.12.2018
Keywords: 

combinatorial reconfiguration, graph algorithm, graph coloring 
Seminar: 

29th International Symposium on Algorithms and Computation (ISAAC 2018)

Issue date: 

2018 
Date of publication: 

06.12.2018 