The complexity of (list) edge-coloring reconfiguration problem

DOI10.1007/978-3-319-53925-6_27zbMATH Open1485.68195OpenAlexW3149314075MaRDI 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)

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

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)

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

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

Cites work

• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Finding shortest paths between graph colourings
• Linear-time algorithm for sliding tokens on trees
• On the complexity of reconfiguration problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Parameterized complexity of graph constraint logic
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Reconfiguration in bounded bandwidth and tree-depth
• Reconfiguration of cliques in a graph
• Reconfiguration of list edge-colorings in a graph
• Relationships between nondeterministic and deterministic tape complexities
• The complexity of bounded length graph recoloring and CSP reconfiguration
• The complexity of change
• The list coloring reconfiguration problem for bounded pathwidth graphs

Cited in

(9)

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

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)