Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters

DOI10.4230/LIPICS.MFCS.2017.51zbMATH Open1441.68109OpenAlexW2964264940MaRDI QIDQ5111266FDOQ5111266

Authors Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

Publication date 26 May 2020

Full work available at URL https://arxiv.org/abs/1705.07551

zbMATH Keywords

graph algorithmlist coloringfixed-parameter tractabilityW[1-hardness]combinatorial reconfiguration

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)

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 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 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.

Recommendations

• Parameterized complexity of the list coloring reconfiguration problem with graph parameters
• The list coloring reconfiguration problem for bounded pathwidth graphs
• The complexity of (list) edge-coloring reconfiguration problem
• Fixed-parameter tractability of \((n-k)\) list coloring
• Finding shortest paths between graph colourings

Cites work

• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• A dichotomy theorem for circular colouring reconfiguration
• A survey of the algorithmic aspects of modular decomposition
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Finding shortest paths between graph colourings
• Homomorphism reconfiguration via homotopy
• Implicat Representation of Graphs
• Linear-time modular decomposition of directed graphs
• On the complexity of reconfiguration problems
• Parameterized Algorithms for Modular-Width
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Recoloring graphs via tree decompositions
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Reconfiguration in bounded bandwidth and tree-depth
• The complexity of bounded length graph recoloring and CSP reconfiguration
• The complexity of change
• The list coloring reconfiguration problem for bounded pathwidth graphs
• Transitiv orientierbare Graphen

Cited in

(8)

• Incremental list coloring of graphs, parameterized by conservation
• The list coloring reconfiguration problem for bounded pathwidth graphs
• Parameterized complexity of optimizing list vertex-coloring through reconfiguration
• Incremental list coloring of graphs, parameterized by conservation
• The complexity of (list) edge-coloring reconfiguration problem
• Introduction to reconfiguration
• The complexity of bounded length graph recoloring and CSP reconfiguration
• Parameterized complexity of the list coloring reconfiguration problem with graph parameters

This page was built for publication: Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111266)