Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances

DOI10.1016/J.TCS.2009.08.023zbMath1177.05112OpenAlexW2036323482MaRDI QIDQ1034528

Luis Cereceda, Paul Bonsma

Publication date: 6 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.08.023

zbMATH Keywords

PSPACE-completecolour graphsuperpolynomial distancevertex-recolouring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Connectedness of the graph of vertex-colourings
• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Mixing 3-Colourings in Bipartite Graphs
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

Related Items (90)

Connected \(k\)-dominating graphs ⋮ Paths between colourings of sparse graphs ⋮ A polynomial version of Cereceda's conjecture ⋮ Ground State Connectivity of Local Hamiltonians ⋮ The Complexity of Dominating Set Reconfiguration ⋮ A dichotomy theorem for circular colouring reconfiguration ⋮ Finding shortest paths between graph colourings ⋮ Parameterized complexity of the list coloring reconfiguration problem with graph parameters ⋮ Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings ⋮ Square-free graphs are multiplicative ⋮ Reconfiguration of dominating sets ⋮ Reconfiguration on nowhere dense graph classes ⋮ Reconfiguring dominating sets in some well-covered and other classes of graphs ⋮ Reconfiguration graphs of shortest paths ⋮ Shortest reconfiguration of sliding tokens on subclasses of interval graphs ⋮ The connectivity of Boolean satisfiability: dichotomies for formulas and circuits ⋮ Finding Shortest Paths Between Graph Colourings ⋮ Reconfiguration of Vertex Covers in a Graph ⋮ The complexity of rerouting shortest paths ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ ZDD-based algorithmic framework for solving shortest reconfiguration problems ⋮ Optimally reconfiguring list and correspondence colourings ⋮ On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets ⋮ Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs ⋮ Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ Parameterized complexity of optimizing list vertex-coloring through reconfiguration ⋮ Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$ ⋮ Parameterized complexity of independent set reconfiguration problems ⋮ Fast recoloring of sparse graphs ⋮ Digraph redicolouring ⋮ Recolouring homomorphisms to triangle-free reflexive graphs ⋮ On the complexity of reconfiguration problems ⋮ Reconfiguration of vertex colouring and forbidden induced subgraphs ⋮ Decremental optimization of vertex-coloring under the reconfiguration framework ⋮ Computational complexity of jumping block puzzles ⋮ Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs ⋮ Complexity of independent set reconfigurability problems ⋮ The Complexity of (List) Edge-Coloring Reconfiguration Problem ⋮ On a conjecture of Mohar concerning Kempe equivalence of regular graphs ⋮ Unnamed Item ⋮ Finding paths between 3-colorings ⋮ Shortest Paths between Shortest Paths and Independent Sets ⋮ Approximability of the subset sum reconfiguration problem ⋮ Linear-time algorithm for sliding tokens on trees ⋮ Redicolouring digraphs: directed treewidth and cycle-degeneracy ⋮ Approximability of the Subset Sum Reconfiguration Problem ⋮ An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree ⋮ Recolouring reflexive digraphs ⋮ List recoloring of planar graphs ⋮ Reconfiguring graph homomorphisms on the sphere ⋮ The complexity of dominating set reconfiguration ⋮ Reconfiguration of list \(L(2,1)\)-labelings in a graph ⋮ On the parameterized complexity of reconfiguration problems ⋮ The \(k\)-dominating graph ⋮ Reconfiguration of list edge-colorings in a graph ⋮ Shortest paths between shortest paths ⋮ Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles ⋮ On k-Total Dominating Graphs ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Reconfiguring spanning and induced subgraphs ⋮ Reconfiguration of homomorphisms to reflexive digraph cycles ⋮ Dominating sets reconfiguration under token sliding ⋮ Recoloring some hereditary graph classes ⋮ Reconfiguration graph for vertex colourings of weakly chordal graphs ⋮ Hamiltonian cycle reconfiguration with answer set programming ⋮ Recongo: bounded combinatorial reconfiguration with answer set programming ⋮ Computational complexity of jumping block puzzles ⋮ Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis ⋮ The Hamiltonian path graph is connected for simple \(s,t\) paths in rectangular grid graphs ⋮ Homomorphism Reconfiguration via Homotopy ⋮ (Lack of) model structures on the category of graphs ⋮ Diameter of colorings under Kempe changes ⋮ Reconfiguring vertex colourings of 2-trees ⋮ Reconfiguration graph for vertex colourings of weakly chordal graphs ⋮ Hard problems that quickly become very easy ⋮ Distributed Recoloring ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ Algorithms for Coloring Reconfiguration Under Recolorability Constraints ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Recognizing Graphs Close to Bipartite Graphs ⋮ Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters ⋮ Hedetniemi's Conjecture and Strongly Multiplicative Graphs ⋮ Irredundance graphs ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs ⋮ Introduction to reconfiguration ⋮ On reconfigurability of target sets ⋮ Complexity of Coloring Reconfiguration under Recolorability Constraints ⋮ ON THE COMPUTATIONAL COMPLEXITY OF ROUTING IN FAULTY K-ARY N-CUBES AND HYPERCUBES

This page was built for publication: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances