The complexity of (list) edge-coloring reconfiguration problem

DOI10.1007/978-3-319-53925-6_27zbMATH Open1485.68195arXiv1609.00109OpenAlexW3149314075MaRDI QIDQ2980922FDOQ2980922

Authors: Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou 

Publication date: 5 May 2017

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Abstract: Let $G$ be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of $k$ colors. Suppose that we are given two list edge-colorings $f_0$ and $f_r$ of $G$, and asked whether there exists a sequence of list edge-colorings of $G$ between $f_0$ and $f_r$ such that each list edge-coloring can be obtained from the previous one by changing a color assignment of exactly one edge. This problem is known to be PSPACE-complete for every integer $kge6$ and planar graphs of maximum degree three, but any complexity hardness was unknown for the non-list variant. In this paper, we first improve the known result by proving that, for every integer $kge4$, the problem remains PSPACE-complete even if an input graph is planar, bounded bandwidth, and of maximum degree three. We then give the first complexity hardness result for the non-list variant: for every integer $kge5$, we prove that the non-list variant is PSPACE-complete even if an input graph is planar, of bandwidth linear in $k$, and of maximum degree $k$.

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

Recommendations

• Reconfiguration of List Edge-Colorings in a Graph
• Reconfiguration of list edge-colorings in a graph
• The list coloring reconfiguration problem for bounded pathwidth graphs
• Parameterized complexity of the list coloring reconfiguration problem with graph parameters
• Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The complexity of change
• Finding paths between 3-colorings
• 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
• Finding shortest paths between graph colourings
• On the complexity of reconfiguration problems
• Reconfiguration of list edge-colorings in a graph
• Linear-time algorithm for sliding tokens on trees
• Reconfiguration of Cliques in a Graph
• Parameterized Complexity of Graph Constraint Logic
• Reconfiguration in bounded bandwidth and tree-depth
• The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs

Cited In (8)

• Reconfiguration of List Edge-Colorings in a Graph
• Parameterized complexity of optimizing list vertex-coloring through reconfiguration
• Parameterized complexity of the list coloring reconfiguration problem with graph parameters
• Introduction to reconfiguration
• NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
• Reconfiguration of list edge-colorings in a graph
• An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree
• Complexity of Hamiltonian cycle reconfiguration

This page was built for publication: The complexity of (list) edge-coloring reconfiguration problem

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