In computational complexity theory and combinatorics, the token reconfiguration problem is a reconfiguration problem on a graph with both an initial and desired state for tokens. Given a graph G {\displaystyle G} , an initial state of tokens is defined by a subset V ⊂ V ( G ) {\displaystyle V\subset V(G)} of the vertices of the graph; let n = | V | {\displaystyle n=|V|} . Moving a token from vertex v 1 {\displaystyle v_{1}} to vertex v 2 {\displaystyle v_{2}} is valid if v 1 {\displaystyle v_{1}} and v 2 {\displaystyle v_{2}} are joined by a path in G {\displaystyle G} that does not contain any other tokens; note that the distance traveled within the graph is inconsequential, and moving a token across multiple edges sequentially is considered a single move. A desired end state is defined as another subset V ′ ⊂ V ( G ) {\displaystyle V'\subset V(G)} . The goal is to minimize the number of valid moves to reach the end state from the initial state.
Motivation The problem is motivated by so-called sliding puzzles, which are in fact a variant of this problem, often restricted to rectangular grid graphs with no holes. The most famous such puzzle, the 15 puzzle, is a variant of this problem on a 4 by 4 grid graph such that n = | V ( G ) | − 1 {\displaystyle n=|V(G)|-1} . One key difference between sliding block puzzles and the token reconfiguration problem is that in the original token reconfiguration problem, the tokens are indistinguishable. As a result, if the graph is connected, the token reconfiguration problem is always solvable; this is not necessarily the case for sliding block puzzles.
Complexity Calinescu, Dumitrescu, and Pach have shown several results regarding both the optimization and approximation of this problem on various types of graphs.
Optimization Firstly, reducing to the case of trees, there is always a solution in at most n {\displaystyle n} moves, with at most one move per token. Furthermore, an optimal solution can be found in time linear in the size of the tree. Clearly, the first result extends to arbitrary graphs; the latter does not. A sketch of the optimal algorithm for trees is as follows. First, we obtain an algorithm that moves each node exactly once, which may not be optimal. Do this recursively: consider any leaf of the smallest tree in the graph containing both the initial and desired sets. If a leaf of this tree is in both, remove it and recurse down. If a leaf is in the initial set only, find a path from it to a vertex in the desired set that does not pass through any other vertices in the desired set. Remove this path (it'll be the last move), and recurse down. The other case, where the leaf is in the desired set only, is symmetric. To extend to an algorithm that achieves the optimum, consider any token in both the initial and desired sets. If removing it would split the graph into subtrees, all of which have the same number of elements from the initial and desired sets, then do so and recurse. If there is no such token, then each token must move exactly once, and so the solution that moves all tokens exactly once must be optimal. While the algorithm for finding the optimum on trees is linear time, finding the optimum for general graphs is NP-complete, a leap up in difficulty. It is in NP; the certificate is a sequence of moves, which is at most linear size, so it remains to show the problem is NP-hard as well. This is done via reduction from set cover. Consider an instance of set cover, where we wish to cover all elements v 1 , v 2 , … , v n {\displaystyle v_{1},v_{2},\ldots ,v_{n}} in a universe U {\displaystyle U} using subsets S 1 , S 2 , … , S m {\displaystyle S_{1},S_{2},\ldots ,S_{m}} of U {\displaystyle U} using the minimum number of subsets. Construct a graph as follows: Make a vertex for each of the elements in the universe and each of the subsets. Connect a subset vertex to an element vertex if the subset contains that element. Create a long path of size n {\displaystyle n} , and attach one end to every subset vertex. The initial set is the added path plus every subset vertex, and the final set is every subset vertex plus every element vertex. To see why this is a reduction, consider the selection of which subset vertex tokens to move. Clearly, we must open up paths to each of the element vertices, and we do so by moving some of the subset vertex tokens. After doing so, each token on the long path must move once. Thus, the optimum cost is equal to the number of selected subsets plus the number of elements (the latter of which is notably a constant). So we have a polynomial-time reduction from set cover, which is NP-complete, to token reconfiguration. Thus token reconfiguration is also NP-complete on general graphs.
… excerpt ends here. Continue reading the full article.
