# Introduction to Reconfiguration
## 2 Specifying and Analyzing Reconfiguration Graphs
### Defining Feasible Solutions and Adjacency  
For many graph problems, a feasible solution can be represented as a subset of the vertices in the instance, or equivalently as the placement of a set of tokens on a subset of the vertices. Reconfiguration steps can then be described with respect to the placement of the tokens. In _token sliding (TS)_, a step can be seen as the sliding of a token along an edge [16]. Two solutions are adjacent under token sliding if they have the same cardinality, the size of their intersection is one less than the size of the solutions, and the two vertices not in the intersection are connected by an edge. If we remove the constraint that the vertices outside the intersection be connected, the adjacency relationship is known as _token_jumping (TJ)_[17]. More formally, two solutions are adjacent under token jumping if they have the same cardinality and the size of the intersection is one less than the size of the solutions. Both token sliding and token jumping can be viewed as the replacement of a vertex in one solution with a vertex outside the solution. If we instead allow a token to be either added or removed at each reconfiguration step, we are considering the adjacency relation of _token addition/removal (TAR)_[4]. Whereas all solutions are of the same size under TS and TJ, under TAR the sizes of solutions can differ. To avoid triviality, sizes are bounded below for maximization problems and bounded above for minimization problems under TAR. To illustrate the need for bounds on solution sizes, we consider the example of Vertex Cover Reconfiguration under TAR, in which each feasible solution is a _vertex cover_ (a set of vertices containing at least one endpoint of each edge) of any size, and two solutions are adjacent if they differ by a single vertex. As there is no bound on size, one of the solutions, the maximum vertex cover, consists of all the vertices in the graph. Finding a path in the graph between any two vertex covers \(s\) and \(t\) is then trivial; by adding vertices one by one, we can form a path from any vertex cover to the maximum vertex cover, and by deleting vertices one by one, we can form a path from the maximum vertex cover to any vertex cover. We can then obtain a path from \(s\) to the maximum vertex cover to \(t\) (Figure 1(a)). As seen in Figure 1(b), placing a bound on the size of a solution may mean that there is no path between \(s\) and \(t\). For solutions that cannot be expressed as subsets of vertices, most definitions of reconfiguration steps entail a single change to a solution. In the source problem Shortest Path, a solution is typically given as a sequence, rather than a set, of vertices forming a shortest path, as there may be more than one shortest path in the graph induced on a subset of vertices [18]; two solutions are adjacent if they differ by a single vertex. For Satisfiability Reconfiguration, each solution is an assignment of variables to the values true and false such that the instance formula evaluates to true; the reconfiguration step is the changing of the value of a single variable. For problems related to coloring of vertices or edges, a solution is an assignment of colors to vertices or edges, and a reconfiguration step involves changing the color of a single entity. Relatively little work has been done on reconfiguration steps that allow multiple changes at once, such as in _Multiple Token Jumping_ (MTJ) [19] or in coloring multiple vertices at once [20]; the modification with most attention thus far is Kempe changes (Section 6.2). For many source problems with solutions that are represented as sequences, unlike for Shortest Path, solutions will typically differ by more than the replacement of a single item in the sequence. For example, for String Editing, an instance is a pair of strings \(s\) and \(t\) and each solution is a sequence of edit operations, such as addition, deletion, and changing of symbols, that transforms \(s\) into \(t\).