Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno:

Approximation and hardness for token swapping

Abstract

We are given a graph with n vertices V={1,…,n}. On each vertex, a distict token from the set {T₁,…,T_n} is placed. A swap is an exchange of tokens between adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that each token T_i is on vertex i. We are able to achieve essentially matching upper and lower bounds, for exact algorithms and approximation algorithms. For exact algorithms, we rule out 2^o(n) algorithms under the Exponential Time Hypothesis (ETH). This is matched with a simple 2^{O(n log n)} algorithm based on exploring the state space. We give a general 4-approximation algorithm and show APX-hardness. Thus, there is a constant δ>1 such that every polynomial-time approximation algorithm has approximation factor at least δ.

Our results also hold for a generalized version, where tokens and vertices are colored. In this generalized version each token must go to a vertex with the same color.