# Introduction to Reconfiguration
## 8 Shortest Transformation  
Shortest transformation is a logical direction for investigation for problems once reachability has been solved, or as an outgrowth of work on reachability. We can find a lower bound on the length of a reconfiguration sequence in a simple way: we focus only on the type of reconfiguration step, and determine the number of steps required to change the source solution to the target solution, ignoring the feasibility of solutions as well as the source problem. For example, under TAR, the minimum number of steps is the number of vertices in the source solution but not the target solution (all of which need to be removed) plus the number of vertices in the target solution but not the source solution (all of which need to be added). For TS or TJ, the minimum number of steps is the number of vertices that differ in the source and target solutions. More generally, we refer to the parts of the solution that differ in the source and target solutions as the _symmetric difference_. Many of the algorithmic results on shortest transformation for special graphs classes result from the observation that reachability can be solved by changing only the symmetric difference. This raises the question of whether shortest transformation is possible in situations where it is necessary to change parts of the solutions outside of the symmetric difference. The question is answered in the analysis of Satisfiability Reconfiguration, for which we consider the dividing lines between tractability and intractability of the source problem as well as for reachability and shortest transformation. Given that Satisfiability is NP-complete, it is not surprising to discover that reachability of Satisfiability Reconfiguration is PSPACE-complete [34]. To determine the dividing line between tractable and intractable classes of formulas for reachability, researchers have built on [PERSON]'s dichotomy theorem [129] for the classical problem of Satisfiability. [PERSON] [129] introduced a framework for expressing formulas in terms of Boolean relations, and proved the problem is in P for instances built from _Schaefer relations_ and NP-complete for all other formulas in the framework. In work by [PERSON] et al. [34], later corrected by [PERSON] [130], an analogous dichotomy theorem was obtained for the reachability problem. By defining the class of _tight relations_, a superset of the Schaefer relations, the authors were able to show that reachability is in P for formulas built from tight relations and PSPACE-complete for all other formulas in the framework. Moreover, they proved a dichotomy theorem for the connectivity problem, where the problem is in coNP for formulas built from tight relations and PSPACE-complete for all other formulas in the framework, and showed that the diameter of connected components is linear for tight relations but can be exponential otherwise. Subsequent work showed that reachability is co-NP-complete for some of the Schaefer relations (Horn and dual Horn) [131], that connectivity can be solved in polynomial time given a characteristic set of Horn relations [131], and that there is an exact algorithm for connectivity [132]. [PERSON], [PERSON], [PERSON], and [PERSON] [133] considered shortest transformation, and obtained a trichotomy, based on both tight relations and _navigable_ relations, a subset of tight relations. They showed that the problem is in P for formulas built from navigable relations, NP-complete for formulas built from relations that are tight but not navigable, and PSPACE-complete otherwise. Of particular significance is the fact that the shortest transformation result holds even though more than the symmetric difference of the source and target solutions may need to be changed in the reconfiguration sequence.