TY - GEN
T1 - Parameterized complexity of the list coloring reconfiguration problem with graph parameters
AU - Hatanaka, Tatsuhiko
AU - Ito, Takehiro
AU - Zhou, Xiao
N1 - Funding Information:
∗ This work is partially supported by JST CREST Grant Number JPMJCR1402, and by JSPS KAKENHI Grant Numbers JP16J02175, JP16K00003, and JP16K00004. † A full version of the paper is available at https://arxiv.org/abs/1705.07551.
Publisher Copyright:
© Tatsuhiko Hatanaka, Takehiro Ito, and Xiao Zhou; licensed under Creative Commons License CC-BY.
PY - 2017/11/1
Y1 - 2017/11/1
N2 - 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 fixed-parameter tractability of the problem when parameterized by several graph parameters. We first give a fixed-parameter algorithm for the problem when parameterized by k and the modular-width of an input graph. We next give a fixed-parameter 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 fixed-parameter 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.
AB - 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 fixed-parameter tractability of the problem when parameterized by several graph parameters. We first give a fixed-parameter algorithm for the problem when parameterized by k and the modular-width of an input graph. We next give a fixed-parameter 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 fixed-parameter 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.
KW - Combinatorial reconfiguration
KW - Fixed-parameter tractability
KW - Graph algorithm
KW - List coloring
KW - W[1]-hardness
UR - http://www.scopus.com/inward/record.url?scp=85038428852&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85038428852&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2017.51
DO - 10.4230/LIPIcs.MFCS.2017.51
M3 - Conference contribution
AN - SCOPUS:85038428852
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
A2 - Larsen, Kim G.
A2 - Raskin, Jean-Francois
A2 - Bodlaender, Hans L.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
Y2 - 21 August 2017 through 25 August 2017
ER -