Document Open Access Logo

Hardness of Token Swapping on Trees

Authors Oswin Aichholzer, Erik D. Demaine , Matias Korman, Anna Lubiw , Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, Nicole Wein

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.3.pdf
  • Filesize: 1.34 MB
  • 15 pages

Document Identifiers

Author Details

Oswin Aichholzer
  • Technische Universität Graz, Austria
Erik D. Demaine
  • CSAIL, Massachusetts Institute of Technology, Cambridge, MA, USA
Matias Korman
  • Siemens Electronic Design Automation, Wilsonville, OR, USA
Anna Lubiw
  • Cheriton School of Computer Science, University of Waterloo, Canada
Jayson Lynch
  • Cheriton School of Computer Science, University of Waterloo, Canada
Zuzana Masárová
  • IST Austria, Klosterneuburg, Austria
Mikhail Rudoy
  • LeapYear Technologies, San Francisco, CA, USA
Virginia Vassilevska Williams
  • CSAIL, Massachusetts Institute of Technology, Cambridge, MA, USA
Nicole Wein
  • DIMACS, Rutgers University, Piscataway, NJ, USA

Funding

  • Lubiw, Anna: Supported by the Natural Sciences and Engineering Research Council of Canada (NSERC).
  • Lynch, Jayson: Supported by the Natural Sciences and Engineering Research Council of Canada (NSERC).
  • Masárová, Zuzana: Supported by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.
  • Vassilevska Williams, Virginia: 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.
  • Wein, Nicole: Supported by a grant to DIMACS from the Simons Foundation (820931). This work was done while the author was at MIT.

Acknowledgements

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.

Cite As Get BibTex

Oswin Aichholzer, 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 (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.3

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Sorting
  • Token swapping
  • Trees
  • NP-hard
  • Approximation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Oswin Aichholzer, Erik D. Demaine, Matias Korman, Jayson Lynch, Anna Lubiw, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, and Nicole Wein. Hardness of token swapping on trees. CoRR, abs/2103.06707, 2021. URL: http://arxiv.org/abs/2103.06707.
  2. Sheldon B. Akers and Balakrishnan Krishnamurthy. A group-theoretic model for symmetric interconnection networks. IEEE Transactions on Computers, 38(4):555-566, 1989. Google Scholar
  3. Noga Alon, F. R. K. Chung, and R. L. Graham. Routing permutations on graphs via matchings. SIAM Journal on Discrete Mathematics, 7(3):513-530, 1994. URL: https://doi.org/10.1137/S0895480192236628.
  4. Amihood Amir and Benny Porat. On the hardness of optimal vertex relabeling and restricted vertex relabeling. In Symposium on Combinatorial Pattern Matching (CPM), volume 9133 of Lecture Notes in Computer Science, pages 1-12. Springer, 2015. Google Scholar
  5. Indranil Banerjee and Dana Richards. New results on routing via matchings on graphs. In R. Klasing and M. Zeitoun, editors, Proceedings of the 21st International Symposium on Fundamentals of Computation Theory, volume 10472 of Lecture Notes in Computer Science, 2017. Google Scholar
  6. Ahmad Biniaz, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. Token swapping on trees. arXiv preprint, 2019. URL: http://arxiv.org/abs/1903.06981.
  7. Édouard Bonnet, Tillmann Miltzow, and Paweł Rzążewski. Complexity of token swapping and its variants. Algorithmica, 80(9):2656-2682, 2018. Google Scholar
  8. Arthur Cayley. LXXVII. Note on the theory of permutations. Philosophical Magazine Series 3, 34(232):527-529, 1849. Google Scholar
  9. Arthur Cayley. Desiderata and suggestions: No. 2. the theory of groups: graphical representation. American Journal of Mathematics, 1(2):174-176, 1878. Google Scholar
  10. Bhadrachalam Chitturi and Priyanshu Das. Sorting permutations with transpositions in O(n³) amortized time. Theoretical Computer Science, 766:30-37, 2019. URL: https://doi.org/10.1016/j.tcs.2018.09.015.
  11. Bhadrachalam Chitturi and Indulekha T S. Sorting permutations with a transposition tree. arXiv preprint, 2018. URL: http://arxiv.org/abs/1811.07443.
  12. Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Christian Scheffer, and Henk Meijer. Coordinated motion planning: Reconfiguring a swarm of labeled robots with bounded stretch. In Proceedings of the 34th International Symposium on Computational Geometry, pages 29:1-29:15, June 2018. Google Scholar
  13. Ashwin Ganesan. An efficient algorithm for the diameter of Cayley graphs generated by transposition trees. International Journal of Applied Mathematics, 42(4), 2012. URL: http://arxiv.org/abs/1202.5888.
  14. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco, 1979. Google Scholar
  15. Michael R. Garey, David S. Johnson, Gary L. Miller, and Christos H. Papadimitriou. The complexity of coloring circular arcs and chords. SIAM Journal on Algebraic Discrete Methods, 1(2):216-227, 1980. Google Scholar
  16. Laurent Gourvès, Julien Lesca, and Anaëlle Wilczynski. Object allocation via swaps along a social network. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 213-219, 2017. URL: https://www.ijcai.org/Proceedings/2017/0031.pdf.
  17. Mark R. Jerrum. The complexity of finding minimum-length generator sequences. Theoretical Computer Science, 36:265-289, 1985. Google Scholar
  18. Jun Kawahara, Toshiki Saitoh, and Ryo Yoshinaka. The time complexity of permutation routing via matching, token swapping and a variant. Journal of Graph Algorithms and Applications, 23(1):29-70, 2019. Google Scholar
  19. Dohan Kim. Sorting on graphs by adjacent swaps using permutation groups. Computer Science Review, 22:89-105, 2016. Google Scholar
  20. Donald Ervin Knuth. The Art of Computer Programming: Sorting and Searching, volume 3. Addison-Wesley, 2nd edition, 1998. Google Scholar
  21. Benjamin Kraft. Diameters of Cayley graphs generated by transposition trees. Discrete Applied Mathematics, 184:178-188, 2015. Google Scholar
  22. Wei-Tian Li, Linyuan Lu, and Yiting Yang. Routing numbers of cycles, complete bipartite graphs, and hypercubes. SIAM Journal on Discrete Mathematics, 24(4):1482-1494, 2010. URL: https://doi.org/10.1137/090776317.
  23. Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno. Approximation and hardness of token swapping. In Proceedings of the 24th Annual European Symposium on Algorithms, volume 57 of LIPIcs, 2016. Google Scholar
  24. Igor Pak. Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ary trees. Discrete Mathematics, 204(1-3):329-335, 1999. Google Scholar
  25. Frederick J. Portier and Theresa P. Vaughan. Whitney numbers of the second kind for the star poset. European Journal of Combinatorics, 11(3):277-288, 1990. Google Scholar
  26. Pavel Surynek. Multi-agent path finding with generalized conflicts: An experimental study. In Jaap van den Herik, Ana Paula Rocha, and Luc Steels, editors, Revised Selected Papers from the 11th International Conference on Agents and Artificial Intelligence, pages 118-142, February 2019. Google Scholar
  27. Theresa P. Vaughan. Bounds for the rank of a permutation on a tree. Journal of Combinatorial Mathematics and Combinatorial Computing, 10:65-81, 1991. Google Scholar
  28. Theresa P. Vaughan. Factoring a permutation on a broom. Journal of Combinatorial Mathematics and Combinatorial Computing, 30:129-148, 1999. Google Scholar
  29. Theresa P. Vaughan and Frederick J. Portier. An algorithm for the factorization of permutations on a tree. Journal of Combinatorial Mathematics and Combinatorial Computing, 18:11-31, 1995. Google Scholar
  30. Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno. Swapping labeled tokens on graphs. Theoretical Computer Science, 586:81-94, 2015. Google Scholar
  31. Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, and Yushi Uno. Swapping colored tokens on graphs. Theoretical Computer Science, 729:1-10, 2018. Google Scholar
  32. Gaku Yasui, Kouta Abe, Katsuhisa Yamanaka, and Takashi Hirayama. Swapping labeled tokens on complete split graphs. Inf. Process. Soc. Japan. SIG Tech. Rep, 2015(14):1-4, 2015. Google Scholar
  33. Louxin Zhang. Optimal bounds for matching routing on trees. SIAM Journal on Discrete Mathematics, 12(1):64-77, 1999. URL: https://doi.org/10.1137/S0895480197323159.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact