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

DOI10.1016/j.tcs.2009.08.023zbMath1177.05112OpenAlexW2036323482MaRDI QIDQ1034528

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-complete colour graph superpolynomial distance vertex-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)

Related Items

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, Approximability of the Subset Sum Reconfiguration Problem, An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree, Recolouring reflexive digraphs, 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, Reconfiguration graph for vertex colourings of weakly chordal graphs, Computational complexity of jumping block puzzles, 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, 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

Cites Work