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

Approximation and hardness for token swapping

In: "Algorithms—ESA 2016", Proc. 24th Annual European Symposium on Algorithms, Aarhus, 2016. Editors: Piotr Sankowski and Christos Zaroliagis. Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2016, pp. 185:1–185:15. doi:10.4230/LIPIcs.ESA.2016.185, arXiv:1602.05150 [cs.CC]


We are given a graph with n vertices V={1,…,n}. On each vertex, a distict token from the set {T1,…,Tn} 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 Ti 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 2o(n) algorithms under the Exponential Time Hypothesis (ETH). This is matched with a simple 2O(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.

  pdf file (gzipped)
other papers about this subject
Last update: August 3, 2016.