Finding Optimal Solutions to Token Swapping by Conflict-based Search and
  Reduction to SAT
  We study practical approaches to solving the token swapping (TSWAP) problem
optimally in this short paper. In TSWAP, we are given an undirected graph with
colored vertices. A colored token is placed in each vertex. A pair of tokens
can be swapped between adjacent vertices. The goal is to perform a sequence of
swaps so that token and vertex colors agree across the graph. The minimum
number of swaps is required in the optimization variant of the problem. We
observed similarities between the TSWAP problem and multi-agent path finding
(MAPF) where instead of tokens we have multiple agents that need to be moved
from their current vertices to given unique target vertices. The difference
between both problems consists in local conditions that state transitions
(swaps/moves) must satisfy. We developed two algorithms for solving TSWAP
optimally by adapting two different approaches to MAPF - CBS and MDD- SAT. This
constitutes the first attempt to design optimal solving algorithms for TSWAP.
Experimental evaluation on various types of graphs shows that the reduction to
SAT scales better than CBS in optimal TSWAP solving.
