**Reference**:- Oswin Aichholzer, Erik Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masarova, Mikhail Rudoy, Virginia Vassilevska Williams, and Nicole Wein, “Hardness of Token Swapping on Trees”, in
*Proceedings of the 30th Annual European Symposium on Algorithms (ESA 2022)*, LIPIcs, Potsdam, Germany, September 5–7, 2022, 33:1–33:15. **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
, the goal is to use the shortest possible sequence of**(sequential) token swapping**, each of which exchanges the tokens at the two endpoints of an edge of the graph. In**swaps**, the goal is to use the fewest**parallel token swapping**, 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.**rounds**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.

**Comments**:- This paper is also available from LIPIcs.
The full paper is available as arXiv:2103.06707.

**Availability**:- The paper is available in PDF (1122k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.