The complexity of change
From MaRDI portal
Abstract: Many combinatorial problems can be formulated as "Can I transform configuration 1 into configuration 2, if certain transformations only are allowed?". An example of such a question is: given two k-colourings of a graph, can I transform the first k-colouring into the second one, by recolouring one vertex at a time, and always maintaining a proper k-colouring? Another example is: given two solutions of a SAT-instance, can I transform the first solution into the second one, by changing the truth value one variable at a time, and always maintaining a solution of the SAT-instance? Other examples can be found in many classical puzzles, such as the 15-Puzzle and Rubik's Cube. In this survey we shall give an overview of some older and more recent work on this type of problem. The emphasis will be on the computational complexity of the problems: how hard is it to decide if a certain transformation is possible or not?
Many combinatorial problems can be formulated as ``Can I transform configuration 1 into configuration 2 if only certain transformations are allowed? An example of such a question is: given two \(k\)-colourings of a graph, can I transform the first \(k\)-colouring into the second one, by recolouring one vertex at a time and always maintaining a proper \(k\)-colouring? Another example is: given two solutions of a SAT-instance, can I transform the first solution into the second one by changing the truth value one variable at a time and always maintaining a solution of the SAT-instance? Other examples can be found in many classical puzzles, such as the 15-puzzle and Rubik's Cube.NEWLINENEWLINENEWLINE In this survey, an overview of some older and some more recent work on this type of problem is given. The emphasis will be on the computational complexity of the problems: how hard is it to decide if a certain transformation is possible or not?NEWLINENEWLINEFor the entire collection see [Zbl 1286.05002].
Recommendations
- Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
- The coloring reconfiguration problem on specific graph classes
- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
- On the complexity of reconfiguration problems
- On the Complexity of Reconfiguration Problems
Cited in
(only showing first 100 items - show all)- Paths between colourings of sparse graphs
- Parameterized complexity of the list coloring reconfiguration problem with graph parameters
- Reconfiguring minimum dominating sets: the -graph of a tree
- Reconfiguration on nowhere dense graph classes
- The packing number of the double vertex graph of the path graph
- On a conjecture of Mohar concerning Kempe equivalence of regular graphs
- Swapping colored tokens on graphs
- Frozen colourings of bounded degree graphs
- Independent-set reconfiguration thresholds of hereditary graph classes
- On girth and the parameterized complexity of token sliding and token jumping
- Reconfiguring graph homomorphisms on the sphere
- Dominating sets reconfiguration under token sliding
- A Thomassen-type method for planar graph recoloring
- The edge-connectivity of token graphs
- Token sliding on split graphs
- On reconfigurability of target sets
- A polynomial version of Cereceda's conjecture
- TS-reconfiguration of dominating sets in circle and circular-arc graphs
- List-recoloring of sparse graphs
- Invitation to combinatorial reconfiguration
- Reconfiguration of regular induced subgraphs
- Parameterized complexity of reconfiguration of atoms
- Distributed reconfiguration of maximal independent sets
- Parameterized complexity of independent set reconfiguration problems
- An update on reconfiguring 10-colorings of planar graphs
- Recoloring graphs of treewidth 2
- Reconfiguration graph for vertex colourings of weakly chordal 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
- Inferring local transition functions of discrete dynamical systems from observations of system behavior
- Rerouting shortest paths in planar graphs
- The connectivity of token graphs
- A proof of the orbit conjecture for flipping edge-labelled triangulations
- Reconfiguration of maximum-weight b-matchings in a graph
- Reconfiguration of colorable sets in classes of perfect graphs
- Complexity of Hamiltonian cycle reconfiguration
- Reconfiguring 10-colourings of planar graphs
- On Vizing's edge colouring question
- Recolouring homomorphisms to triangle-free reflexive graphs
- Decremental optimization of vertex-coloring under the reconfiguration framework
- Reconfiguration of cliques in a graph
- Reconfiguration of Steiner trees in an unweighted graph
- Independent set reconfiguration in cographs and their generalizations
- Classifying coloring graphs
- Finding shortest paths between graph colourings
- Degree-constrained subgraph reconfiguration is in P
- The complexity of (list) edge-coloring reconfiguration problem
- Sliding tokens on block graphs
- A dichotomy theorem for circular colouring reconfiguration
- Finding shortest paths between graph colourings
- scientific article; zbMATH DE number 5671596 (Why is no real title available?)
- The complexity of dominating set reconfiguration
- Square-free graphs are multiplicative
- Mixing homomorphisms, recolorings, and extending circular precolorings
- On limitations of transformations between combinatorial problems
- Frozen (+1)-colourings of bounded degree graphs
- Congestion-free rerouting of flows on DAGs
- Reconfiguration of graph minors
- Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
- Shortest reconfiguration of perfect matchings via alternating cycles
- Shortest reconfiguration of perfect matchings via alternating cycles
- Token sliding on split graphs
- Algorithms for Coloring Reconfiguration Under Recolorability Constraints
- Distributed Reconfiguration of Maximal Independent Sets
- Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
- The Perfect Matching Reconfiguration Problem
- Independence and matching numbers of some token graphs
- Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
- Reconfiguration of Colorable Sets in Classes of Perfect Graphs
- Complexity of coloring reconfiguration under recolorability constraints
- The complexity of dominating set reconfiguration
- Hamiltonicity of token graphs of fan graphs
- Shortest reconfiguration paths in the solution space of Boolean formulas
- Reconfiguration of Spanning Trees with Many or Few Leaves
- Recoloring Planar Graphs of Girth at Least Five
- Kempe equivalence of colourings of cubic graphs
- Incremental optimization of independent sets under the reconfiguration framework
- Diameter of colorings under Kempe changes
- Kempe equivalence of colourings of cubic graphs
- Fixed-parameter algorithms for graph constraint logic
- Token sliding on graphs of girth five
- Token Swapping on Trees
- Kempe equivalence of 4‐critical planar graphs
- Loopless algorithms to generate maximum length Gray cycles wrt. \(k\)-character substitutions
- Reconfiguration of spanning trees with degree constraints or diameter constraints
- ZDD-based algorithmic framework for solving shortest reconfiguration problems
- Optimally reconfiguring list and correspondence colourings
- Feedback vertex set reconfiguration in planar graphs
- Inapproximability of shortest paths on perfect matching polytopes
- Linear transformations between dominating sets in the TAR-model
- scientific article; zbMATH DE number 7765402 (Why is no real title available?)
- Fixed-parameter algorithms for graph constraint logic
- scientific article; zbMATH DE number 7764115 (Why is no real title available?)
- On the longest flip sequence to untangle segments in the plane
- Reconfiguration of vertex-disjoint shortest paths on graphs
- On the complexity of distance-\(d\) independent set reconfiguration
- Parameterized complexity of optimizing list vertex-coloring through reconfiguration
- Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$
- Galactic token sliding
This page was built for publication: The complexity of change
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875857)
