Approximation and Hardness for Token Swapping

Tillmann Miltzow, Lothar Narins, Yoshio Okamoto +3

Given a graph $G=(V,E)$ with $V=\{1,\dots ,n\}$, we place on every vertex a token $T_1,\dots ,T_n$. A swap is an exchange of tokens on adjacent vertices. We consider the algorithmi…