Token reconfiguration

Firstly, reducing to the case of trees, there is always a solution in at most ${\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 ${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$ in a universe ${\displaystyle U}$ using subsets ${\displaystyle S_{1},S_{2},\ldots ,S_{m}}$ of ${\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 ${\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.

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. The reduction is the same one as above, from set cover. However, the set cover problem is restricted to subsets of size at most 3, which is an APX-hard problem.[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. Thus, the constants from the L-reduction are ${\displaystyle \alpha =1/4,\beta =1}$.

One can, in fact, modify the reduction to work for labeled token reconfiguration as well. To do so, attach a new vertex to each of the subset vertices, which is neither an initial nor desired vertex. Label the vertices on the long path 1 through ${\displaystyle n}$, and do the same for the element vertices. 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. This is an L-reduction with ${\displaystyle \alpha =1/5,\beta =2}$.

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. The proof is much more complicated and omitted here.