The complexity of change
Jan van den Heuvel · Cambridge University Press eBooks · 2013
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. In this survey we shall give an overview of some older and some 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? Introduction Reconfiguration problems are combinatorial problems in which we are given a collection of configurations, together with some transformation rule(s) that allows us to change one configuration to another. A classic example is the so-called 15- puzzle (see Figure 1): 15 tiles are arranged on a 4 × 4 grid, with one empty square; neighbouring tiles can be moved to the empty slot. The normal aim is, given an initial configuration, to move the tiles to the position with all numbers in order (right-hand picture in Figure 1). Readers of a certain age may remember Rubik’s cube and its relatives as examples of reconfiguration puzzles (see Figure 2).