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.
, an initial state of tokens is defined by a subset
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
[1] 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.
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.
Calinescu, Dumitrescu, and Pach have shown several results regarding both the optimization and approximation of this problem on various types of graphs.
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.
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.
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.
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.
Construct a graph as follows: Make a vertex for each of the elements in the universe and each of the subsets.
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.
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.
The token reconfiguration problem is APX-complete, meaning that in some sense, it is as hard to approximate as any problem that has a constant-factor approximation algorithm.
[3] Using exactly the same structure as above, we obtain an L-reduction, as the distance of any solution from optimum is equal between the set cover instance and the transformed token reconfiguration problem.
The only change is the addition of the number of elements in the universe.
Furthermore, the set cover optimum is at least 1/3 of the number of elements, due to the bounded subset size.
One can, in fact, modify the reduction to work for labeled token reconfiguration as well.
Now, the solution consists of 'moving aside' each chosen subset vertex token, correctly placing the labeled vertices from the path, and returning the subset vertex tokens to the initial locations.
Calinescu, Dumitrescu, and Pach have also shown that there exists a 3-approximation for unlabeled token reconfiguration, so the problem is in APX as well and thus APX-complete.