2026-07-20T14:50:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8106 2024-03-06T10:40:55Z ddc:004 open_access

Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters Hatanaka, Tatsuhiko Ito, Takehiro Zhou, Xiao combinatorial reconfiguration fixed-parameter tractability graph algorithm list coloring W[1]-hardness 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 PSPACE-complete 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tatsuhiko Hatanaka and Takehiro Ito and Xiao Zhou 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.51 urn:nbn:de:0030-drops-81060 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.51 eng https://creativecommons.org/licenses/by/3.0/legalcode