Hatanaka, Tatsuhiko ;
Ito, Takehiro ;
Zhou, Xiao
Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
Abstract
Let G be a graph such that each vertex has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. For two given list colorings of G, we study the problem of transforming one into the other by changing only one vertex color assignment at a time, while at all times maintaining a list coloring. This problem is known to be PSPACEcomplete even for bounded bandwidth graphs and a fixed constant k. In this paper, we study the fixedparameter tractability of the problem when parameterized by several graph parameters. We first give a fixedparameter algorithm for the problem when parameterized by k and the modularwidth of an input graph. We next give a fixedparameter algorithm for the shortest variant which computes the length of a shortest transformation when parameterized by k and the size of a minimum vertex cover of an input graph. As corollaries, we show that the problem for cographs and the shortest variant for split graphs are fixedparameter tractable even when only k is taken as a parameter. On the other hand, we prove that the problem is W[1]hard when parameterized only by the size of a minimum vertex cover of an input graph.
BibTeX  Entry
@InProceedings{hatanaka_et_al:LIPIcs:2017:8106,
author = {Tatsuhiko Hatanaka and Takehiro Ito and Xiao Zhou},
title = {{Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {51:151:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8106},
URN = {urn:nbn:de:0030drops81060},
doi = {10.4230/LIPIcs.MFCS.2017.51},
annote = {Keywords: combinatorial reconfiguration, fixedparameter tractability, graph algorithm, list coloring, W[1]hardness}
}
01.12.2017
Keywords: 

combinatorial reconfiguration, fixedparameter tractability, graph algorithm, list coloring, W[1]hardness 
Seminar: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Issue date: 

2017 
Date of publication: 

01.12.2017 