# Introduction to Reconfiguration
## 9 Labels and Colors on Tokens
### Placing Tokens on All Vertices  
Inspired by sorting networks, further research has considered the case in which the number of tokens is equal to the number of vertices in the graph. In this case, the reconfiguration step swaps tokens on a pair of adjacent vertices with distinct labels. Research in the area considers two variants: one in which all tokens are distinct, and one in which each token has a specified color, where the number of colors can be smaller than the number of vertices.  
When the tokens are all distinct, the reconfiguration graph is connected and has diameter in \(O(n^{2})\)[155]. Determining the shortest transformation sequence, Token Swapping, is NP-complete [156], even on graphs of treewidth at most two [157], \(W[1]\)-hard with respect to the length of the reconfiguration sequence [157], and inapproximable [156]. Algorithmic results include polynomial-time solutions on paths [82], cycles [82], complete graphs [158], stars [159], complete bipartite graphs [139], and complete split graphs [160], as well as approximation algorithms for squares of paths [161], trees [139; 156], and general graphs [156], fixed-parameter algorithms for nowhere dense graphs, which include planar graphs and graphs of bounded treewidth [157], and exact algorithms (with matching lower bounds) [156].  
In a variant, others consider the problem of shortest transformation when all vertices have tokens, tokens can have different colors, but tokens of the same color are indistinguishable. In contrast to Token Swapping, for which no general hardness result is known, here the problem is NP-complete for at least three colors even for connected planar bipartite graphs of maximum degree four. A polynomial-time algorithm has been found for the case with two colors, and a linear-time algorithm for trees [162]. In addition, it has been shown that the reconfiguration graph is connected when there are at least three colors, \(G\) is not a cycle, and \(G\) has no \((n-n_{r})\)-isthmus (where \(n_{r}\) is the size of the largest color class), and the number of connected components has been determined for various cases [163]. In \"parallel\" variants, swapping is allowed on non-adjacent edges at the same time; the problem of determining the minimum number of swaps needed has been shown to be NP-complete, with a polynomial-time approximation algorithm for paths, and NP-complete for colored tokens, even with as few as two colors [164]. Various results have been shown for a \"subset\" variant, in which each token has a set of possible destinations [157].  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Class** & **Holes** & **Type** & **Problem** & **Result** & **Citation** \\ \hline \(4\times 4\) grid & 1 & distinct & connectivity & not connected & [3] \\ \(n\times n\) grid & 1 & distinct & connectivity & characterized & [147] \\ \(n\times n\) grid & 1 & distinct & diameter & \(\Omega(n^{3})\) & [148] \\ \(n\times n\) grid & 1 & distinct & shortest & NP-complete & [149] \\ \hline any & 1 & distinct & connectivity & characterized & [147] \\ any & 1 & distinct & shortest & NP-complete & [150] \\ any & any & distinct & reachability & \(\Theta(|V(G)|^{3})\) & [151] \\ tree & any & distinct & reachability & \(O(|V(G)|)\) & [152] \\ any & any & distinct & diameter & \(O(|V(G)|^{3})\) & [151] \\ \hline tree & any & robot & shortest & P & [140] \\ any & any & robot & shortest & NP-complete & [140] \\ any & any & colors & reachability & \(O(|V(G)|)\) & [153] \\ any & any & same & shortest & P & [154] \\ any & any & colors & connectivity & characterized & [154] \\ \hline \hline \end{tabular}
\end{table}
Table 2: Results on the 15-puzzle and generalizations.