Symbolic Algorithms for Token Swapping

We study different symbolic algorithms to solve two related reconfiguration problems on graphs: the token swapping problem and the permutation routing via matchings problem. Input to both problems is a connected graph with labeled vertices and a token in each vertex. The goal is to move each token to its destination vertex using swap operations. In the token swapping problem, the goal is to find a solution with a minimum number of swaps. In the permutation routing via matchings problem, the goal is to find a solution with a minimum number of steps, where a step is a set of disjoint swaps which can be performed in parallel. First, we present an A* search algorithm. This algorithm can find optimal solutions if used with an admissible heuristic. We also evaluate the use of non-admissible heuristics. In this case, we prove that the result will deviate from an optimum result by at most an even number of swaps. We also present an algorithm based on Boolean satisfiability. We evaluate our methods on a large set of practical benchmarks.