Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters

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

Authors: Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou 

Publication date: 26 May 2020

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.

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

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

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)

Cites Work

• Transitiv orientierbare Graphen
• The complexity of change
• Finding paths between 3-colorings
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Parameterized Algorithms for Modular-Width
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Homomorphism reconfiguration via homotopy
• A dichotomy theorem for circular colouring reconfiguration
• Finding shortest paths between graph colourings
• Title not available (Why is that?)
• On the complexity of reconfiguration problems
• Implicat Representation of Graphs
• A survey of the algorithmic aspects of modular decomposition
• Linear-time modular decomposition of directed graphs
• Recoloring graphs via tree decompositions
• Reconfiguration in bounded bandwidth and tree-depth
• The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs

Cited In (4)

• Parameterized complexity of optimizing list vertex-coloring through reconfiguration
• Parameterized complexity of the list coloring reconfiguration problem with graph parameters
• Introduction to reconfiguration
• Incremental list coloring of graphs, parameterized by conservation

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)