Token reconfiguration

In computational complexity theory and combinatorics, the token reconfiguration problem is an optimization problem on a graph with both an initial and desired state for tokens.

Given a graph $G$, an initial state of tokens is defined by a subset $V \subset V(G)$ of the vertices of the graph; let $n = |V|$. Moving a token from vertex $v_1$ to vertex $v_2$ is valid if $v_1$ and $v_2$ are joined by a path in $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' \subset V(G)$. The goal is to minimize the number of valid moves to reach the end state from the initial state.^[1]

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$. 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. ^[2]

Optimization

Firstly, reducing to the case of trees, there is always a solution in at most $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, \ldots, v_n$ in a universe $U$ using subsets $S_1, S_2, \ldots, S_m$ of $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$, 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.

Approximation

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 the exact 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 $\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 $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 $\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.

References

1. Demaine, Erik (Fall 2014). "Algorithmic Lower Bounds: Fun with Hardness Proofs Lecture 11 Notes" (PDF).
2. Calinescu, Gruia; Dumitrescu, Adrian; Pach, János (2006). "Reconfigurations in Graphs and Grids". LATIN 2006: Theoretical Informatics, 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006, Proceedings: 262––273. doi:10.1007/11682462_27.
3. Papadimitriou, Christos H.; Yannakakis, Mihailis (1991). "Optimization, Approximation, and Complexity Classes". Journal of Computer and Systems Sciences 43 (3): 425–440. doi:10.1016/0022-0000(91)90023-X.