TY - GEN
T1 - Hardness of Token Swapping on Trees
AU - Aichholzer, Oswin
AU - Demaine, Erik D.
AU - Korman, Matias
AU - Lubiw, Anna
AU - Lynch, Jayson
AU - Masárová, Zuzana
AU - Rudoy, Mikhail
AU - Williams, Virginia Vassilevska
AU - Wein, Nicole
N1 - Publisher Copyright:
© 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2022/9/1
Y1 - 2022/9/1
N2 - 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.
AB - 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.
KW - Approximation
KW - NP-hard
KW - Sorting
KW - Token swapping
KW - Trees
UR - http://www.scopus.com/inward/record.url?scp=85137546139&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ESA.2022.3
DO - 10.4230/LIPIcs.ESA.2022.3
M3 - Conference paper
AN - SCOPUS:85137546139
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 30th Annual European Symposium on Algorithms, ESA 2022
A2 - Chechik, Shiri
A2 - Navarro, Gonzalo
A2 - Rotenberg, Eva
A2 - Herman, Grzegorz
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 30th Annual European Symposium on Algorithms
Y2 - 5 September 2022 through 9 September 2022
ER -