# Introduction to Reconfiguration
## 2 Specifying and Analyzing Reconfiguration Graphs
### Defining Problems  
Viewing reconfiguration as both a sequence of steps and as a path in a graph gives rise to interrelated algorithmic and structural questions. The main focus of algorithmic work has been to determine the existence of paths between solutions in the reconfiguration graph, such as between a starting and ending configuration of the 15-puzzle. More formally, the _reachability problem_ determines whether or not there is a reconfiguration sequence joining two input solutions, sometimes designated as the _source solution_ and _target solution;_ it should be noted that since the reconfiguration graph is undirected, the designation of one input as the source and the other as the target is arbitrary. So prevalent was the focus on the reachability problem that it appears in the literature as the \"reconfigurability problem\" [17] or simply the \"reconfiguration version\" of a problem. There is no need for an algorithm for reachability if one can determine that the reconfiguration graph is connected, and hence that all instances of the reachability problem are yes-instances. For a fixed source problem, instance, definition of feasible solutions, and definition of adjacency, the _connectivity problem_ asks whether the reconfiguration graph is connected. Most work on connectivity focuses on determining properties of the instance that result in the reconfiguration graph being connected rather than the complexity of algorithms used to check those properties. The _shortest transformation_ problem is an extension of reachability, where the goal is to find a shortest reconfiguration sequence between a pair of input solutions. In the related decision problem of _bounded transformation_, the input includes both a pair of solutions and a positive integer bound; the problem is to determine whether the solutions are connected by a sequence of length no greater than the bound. Other terms for these problems that appear in the literature include the _length-bounded version of reachability_, _bounded reconfiguration_, and _shortest path_, not to be confused with the source problem Shortest Path. An upper bound on the length of the shortest transformation can be determined by finding a solution to the structural _diameter_ problem, the problem of determining the diameter of the reconfiguration graph (or of its connected components). Although most of the work on reconfiguration to date has focused on reachability, connectivity, shortest/bounded transformation, and diameter (and, at times, producing an actual reconfiguration sequence, when one exists, typically as a minor extension of the algorithm for the decision problem of reachability), there are also results that consider other structural properties of the reconfiguration graph. We discuss these in more detail in Section 7. A new direction in algorithmic problems is the _optimization_ variant [24], where the goal is to find an optimal solution reachable from a given solution. Various related problems have been considered for the problem of _k-Coloring_, starting with an assignment of colors to vertices that may not form a _proper coloring_ (a coloring in which the endpoints of each edge have different colors). In one case, the graphs are directed, and the goal is to reach a particular proper coloring by giving a vertex a color different from that of its neighbors [25]. In Color-Fixing, starting with an assignment of colors to vertices, the goal is to determine the minimum number of vertex recolorings required in order to find any proper coloring [26]. The examination of the role of reconfiguration steps gives rise to further problems of interest. Reconfiguration steps are _equivalent_ for a given source problem if an instance is solvable using one type of reconfiguration step if and only if it is solvable using another type of reconfiguration step. It has been shown that, for Independent Set Reconfiguration, TJ and TAR are equivalent [17], and, for Clique Reconfiguration, TJ, TS, and TAR are equivalent [27]. For most problems, however, such relationships are unknown.