Document Open Access Logo

Approximation and Hardness of Token Swapping

Authors Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, Takeaki Uno

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.66.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Tillmann Miltzow
Lothar Narins
Yoshio Okamoto
Günter Rote
Antonis Thomas
Takeaki Uno

Cite As Get BibTex

Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno. Approximation and Hardness of Token Swapping. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 66:1-66:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.66

Abstract

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.

Subject Classification

Keywords
  • token swapping
  • minimum generator sequence
  • graph theory
  • NP-hardness
  • approximation algorithms

Metrics

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

References

  1. Sanjeev Arora and Carsten Lund. Hardness of approximations. In Dorit Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, pages 399-446. PWS Publishing, 1996. Google Scholar
  2. Paul Bonsma, Takehiro Ito, Marcin Kamiński, and Naomi Nishimura. Invitation to combinatorial reconfiguration. Presentation at the First International Workshop on Combinatorial Reconfiguration (CoRe 2015), http://www.ecei.tohoku.ac.jp/alg/core2015/page/template.pdf, February 2015.
  3. Paul Bonsma, Marcin Kamiński, and Marcin Wrochna. Reconfiguring independent sets in claw-free graphs. In R. Ravi and Inge Li Gørtz, editors, Algorithm Theory - SWAT 2014, volume 8503 of Lecture Notes in Computer Science, pages 86-97. Springer International Publishing, 2014. URL: http://dx.doi.org/10.1007/978-3-319-08404-6_8.
  4. Arthur Cayley. Note on the theory of permutations. Philosophical Magazine Series 3, 34:527-529, 1849. URL: http://dx.doi.org/10.1080/14786444908646287.
  5. Gruia Călinescu, Adrian Dumitrescu, and János Pach. Reconfigurations in graphs and grids. SIAM Journal on Discrete Mathematics, 22(1):124-138, 2008. URL: http://dx.doi.org/10.1137/060652063.
  6. Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada. Linear-time algorithm for sliding tokens on trees. Theoretical Computer Science, 600:132-142, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.07.037.
  7. Ruy Fabila-Monroy, David Flores-Peñaloza, Clemens Huemer, Ferran Hurtado, Jorge Urrutia, and David R. Wood. Token graphs. Graphs and Combinatorics, 28:365-380, 2012. URL: http://dx.doi.org/10.1007/s00373-011-1055-9.
  8. Eli Fox-Epstein, Duc A. Hoang, Yota Otachi, and Ryuhei Uehara. Sliding token on bipartite permutation graphs. In Khaled Elbassioni and Kazuhisa Makino, editors, Algorithms and Computation, volume 9472 of Lecture Notes in Computer Science, pages 237-247. Springer Berlin Heidelberg, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48971-0_21.
  9. Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, and Christos H. Papadimitriou. The connectivity of Boolean satisfiability: Computational and structural dichotomies. SIAM J. Comput., 38(6):2330-2355, 2009. URL: http://dx.doi.org/10.1137/07070440X.
  10. Daniel Graf. How to sort by walking on a tree. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015, volume 9294 of Lecture Notes in Computer Science, pages 643-655. Springer Berlin Heidelberg, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_54.
  11. Robert A. Hearn and Erik D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1-2):72-96, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2005.05.008.
  12. Lenwood S. Heath and John Paul C. Vergara. Sorting by short swaps. Journal of Computational Biology, 10(5):775-789, 2003. URL: http://dx.doi.org/10.1089/106652703322539097.
  13. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1727.
  14. Mark R. Jerrum. The complexity of finding minimum-length generator sequences. Theoretical Computer Science, 36:265-289, 1985. URL: http://dx.doi.org/10.1016/0304-3975(85)90047-7.
  15. Marcin Kamiński, Paul Medvedev, and Martin Milanič. Complexity of independent set reconfigurability problems. Theoretical Computer Science, 439:9-15, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.03.004.
  16. Donald E. Knuth. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, 1973. Google Scholar
  17. Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno. Approximation and Hardness of Token Swapping. Preprint, February 2016. URL: http://arxiv.org/abs/1602.05150.
  18. Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, and Marcin Wrochna. Reconfiguration over tree decompositions. In Marek Cygan and Pinar Heggernes, editors, Parameterized and Exact Computation, volume 8894 of Lecture Notes in Computer Science, pages 246-257. Springer International Publishing, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13524-3_21.
  19. 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. Selected papers in honor of Henry W. Gould. URL: http://dx.doi.org/10.1016/S0012-365X(98)00377-X.
  20. Daniel Ratner and Manfred Warmuth. The (n²-1)-puzzle and related relocation problems. Journal of Symbolic Computation, 10(2):111-137, 1990. URL: http://dx.doi.org/10.1016/S0747-7171(08)80001-6.
  21. Richard M. Wilson. Graph puzzles, homotopy, and the alternating group. Journal of Combinatorial Theory, Series B, 16(1):86-96, 1974. URL: http://dx.doi.org/10.1016/0095-8956(74)90098-7.
  22. 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. Special issue for the conference Fun with Algorithms 2014. URL: http://dx.doi.org/10.1016/j.tcs.2015.01.052.
  23. Katsuhisa Yamanaka, Takashi Horiyama, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, and Yushi Uno. Swapping colored tokens on graphs. In Frank Dehne, Jörg-Rüdiger Sack, and Ulrike Stege, editors, Algorithms and Data Structures, volume 9214 of Lecture Notes in Computer Science, pages 619-628. Springer International Publishing, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21840-3_51.
  24. Gaku Yasui, Kouta Abe, Katsuhisa Yamanaka, and Takashi Hirayama. Swapping labeled tokens on complete split graphs. SIG Technical Reports, 2015-AL-153(14):1-4, 2015. Google Scholar
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