Hardness of token swapping on trees
Aichholzer O, Demaine ED, Korman M, Lubiw A, Lynch J, Masárová Z, Rudoy M, Vassilevska Williams V, Wein N. 2022. Hardness of token swapping on trees. 30th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 244, 3.
Download
Conference Paper
| Published
| English
Scopus indexed
Author
Aichholzer, Oswin;
Demaine, Erik D.;
Korman, Matias;
Lubiw, Anna;
Lynch, Jayson;
Masárová, ZuzanaISTA ;
Rudoy, Mikhail;
Vassilevska Williams, Virginia;
Wein, Nicole
Corresponding author has ISTA affiliation
Department
Grant
Series Title
LIPIcs
Abstract
Given a graph where every vertex has exactly one labeled token, how can we most quickly execute a given permutation on the tokens? In (sequential) token swapping, the goal is to use the shortest possible sequence of swaps, each of which exchanges the tokens at the two endpoints of an edge of the graph. In parallel token swapping, the goal is to use the fewest rounds, each of which consists of one or more swaps on the edges of a matching. We prove that both of these problems remain NP-hard when the graph is restricted to be a tree. These token swapping problems have been studied by disparate groups of researchers in discrete mathematics, theoretical computer science, robot motion planning, game theory, and engineering. Previous work establishes NP-completeness on general graphs (for both problems), constant-factor approximation algorithms, and some poly-time exact algorithms for simple graph classes such as cliques, stars, paths, and cycles. Sequential and parallel token swapping on trees were first studied over thirty years ago (as "sorting with a transposition tree") and over twenty-five years ago (as "routing permutations via matchings"), yet their complexities were previously unknown. We also show limitations on approximation of sequential token swapping on trees: we identify a broad class of algorithms that encompass all three known polynomial-time algorithms that achieve the best known approximation factor (which is 2) and show that no such algorithm can achieve an approximation factor less than 2.
Publishing Year
Date Published
2022-09-01
Proceedings Title
30th Annual European Symposium on Algorithms
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Acknowledgement
g Anna Lubiw: Supported by the Natural Sciences and Engineering Research Council of
Canada (NSERC). Jayson Lynch: Supported by the Natural Sciences and Engineering Research Council of Canada (NSERC). Zuzana Masárová: Supported by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. Virginia Vassilevska Williams: Supported by an NSF CAREER Award, NSF Grants CCF-1528078, CCF-1514339 and CCF-1909429, a BSF Grant BSF:2012338, a Google Research Fellowship and a Sloan Research Fellowship.
Nicole Wein: Supported by a grant to DIMACS from the Simons Foundation (820931). This work was done while the author was at MIT.
This research was initiated at the 34th Bellairs Winter Workshop on Computational Geometry, co-organized by Erik Demaine and Godfried Toussaint, held on March 22–29,
2019 in Holetown, Barbados. We thank the other participants of that workshop for providing a
stimulating research environment.
Volume
244
Article Number
3
Conference
ESA: European Symposium on Algorithms
Conference Location
Berlin/Potsdam, Germany
Conference Date
2022-09-05 – 2022-09-09
IST-REx-ID
Cite this
Aichholzer O, Demaine ED, Korman M, et al. Hardness of token swapping on trees. In: 30th Annual European Symposium on Algorithms. Vol 244. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.ESA.2022.3
Aichholzer, O., Demaine, E. D., Korman, M., Lubiw, A., Lynch, J., Masárová, Z., … Wein, N. (2022). Hardness of token swapping on trees. In 30th Annual European Symposium on Algorithms (Vol. 244). Berlin/Potsdam, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2022.3
Aichholzer, Oswin, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, and Nicole Wein. “Hardness of Token Swapping on Trees.” In 30th Annual European Symposium on Algorithms, Vol. 244. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.ESA.2022.3.
O. Aichholzer et al., “Hardness of token swapping on trees,” in 30th Annual European Symposium on Algorithms, Berlin/Potsdam, Germany, 2022, vol. 244.
Aichholzer O, Demaine ED, Korman M, Lubiw A, Lynch J, Masárová Z, Rudoy M, Vassilevska Williams V, Wein N. 2022. Hardness of token swapping on trees. 30th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 244, 3.
Aichholzer, Oswin, et al. “Hardness of Token Swapping on Trees.” 30th Annual European Symposium on Algorithms, vol. 244, 3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:10.4230/LIPIcs.ESA.2022.3.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2022_LIPIcS_Aichholzer.pdf
1.41 MB
Access Level
Open Access
Date Uploaded
2024-08-12
MD5 Checksum
a1fbd3e7baad510fbcb998cf4a7d9f7f
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2103.06707