## 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]
### Abstract

We are given a graph with `n` vertices
`V`={1,…,`n`}. On each
vertex, a distict token from the set
{`T`_{1},…,`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.

Last update: August 3, 2016.