2026-07-25T09:10:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6408 2024-03-06T10:38:11Z ddc:004 open_access

Approximation and Hardness of Token Swapping Miltzow, Tillmann Narins, Lothar Okamoto, Yoshio Rote, Günter Thomas, Antonis Uno, Takeaki token swapping minimum generator sequence graph theory NP-hardness approximation algorithms Given a graph G=(V,E) with V={1,...,n}, we place on every vertex a token T_1,...,T_n. A swap is an exchange of tokens on adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that 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 any 2^{o(n)} algorithm under the ETH. This is matched with a simple 2^{O(n*log(n))} algorithm based on a breadth-first search in an auxiliary graph. We show one general 4-approximation and show APX-hardness. Thus, there is a small constant delta > 1 such that every polynomial time approximation algorithm has approximation factor at least delta. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tillmann Miltzow and Lothar Narins and Yoshio Okamoto and Günter Rote and Antonis Thomas and Takeaki Uno 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.66 urn:nbn:de:0030-drops-64084 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.66 eng https://creativecommons.org/licenses/by/3.0/legalcode