Document Open Access Logo

Complexity of Token Swapping and its Variants

Authors Édouard Bonnet, Tillmann Miltzow, Pawel Rzazewski

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.16.pdf
  • Filesize: 0.68 MB
  • 14 pages

Document Identifiers

Author Details

Édouard Bonnet
Tillmann Miltzow
Pawel Rzazewski

Cite As Get BibTex

Édouard Bonnet, Tillmann Miltzow, and Pawel Rzazewski. Complexity of Token Swapping and its Variants. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.16

Abstract

In the Token Swapping problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is W[1]-hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f, it cannot be solved in time f(k)*n^(o(k / log k)) where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial n^O(k)-time algorithm.

We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes.

Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases.

Subject Classification

Keywords
  • token swapping
  • parameterized complexity
  • NP-hardness
  • W[1]-hardness

Metrics

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

References

  1. 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
  2. Elwyn R Berlekamp, John Horton Conway, and Richard K Guy. Winning Ways, for Your Mathematical Plays: Games in particular, volume 2. Academic Pr, 1982. Google Scholar
  3. Hans L. Bodlaender and Jesper Nederlof. Subexponential time algorithms for finding small tree and path decompositions. In ESA 2015 Proc., pages 179-190. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_16.
  4. Prosenjit Bose and Ferran Hurtado. Flips in planar graphs. Computational Geometry, 42(1):60-80, 2009. Google Scholar
  5. Gruia Calinescu, Adrian Dumitrescu, and János Pach. Reconfigurations in graphs and grids. In LATIN 2006 Proc., pages 262-273. Springer, 2006. URL: http://dx.doi.org/10.1007/11682462_27.
  6. Arthur Cayley. LXXVII. Note on the theory of permutations. Philosophical Magazine Series 3, 34(232):527-529, 1849. URL: http://dx.doi.org/10.1080/14786444908646287.
  7. Mark De Berg, Marc Van Kreveld, Mark Overmars, and Otfried Cheong Schwarzkopf. Computational geometry. In Computational geometry, pages 1-17. Springer, 2000. Google Scholar
  8. 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.
  9. Ruy Fabila-Monroy, David Flores-Peñaloza, Clemens Huemer, Ferran Hurtado, Jorge Urrutia, and David R. Wood. Token graphs. Graphs and Combinatorics, 28(3):365-380, 2012. URL: http://dx.doi.org/10.1007/s00373-011-1055-9.
  10. F. Farnoud, C. Y. Chen, O. Milenkovic, and N. Kashyap. A graphical model for computing the minimum cost transposition distance. In Information Theory Workshop (ITW), 2010 IEEE, pages 1-5, Aug 2010. URL: http://dx.doi.org/10.1109/CIG.2010.5592890.
  11. Farzad Farnoud and Olgica Milenkovic. Sorting of permutations by cost-constrained transpositions. IEEE Trans. Information Theory, 58(1):3-23, 2012. URL: http://dx.doi.org/10.1109/TIT.2011.2171532.
  12. 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.
  13. Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci., 38:293-306, 1985. URL: http://dx.doi.org/10.1016/0304-3975(85)90224-5.
  14. Daniel Graf. How to sort by walking on a tree. In ESA 2015 Proc., pages 643-655. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_54.
  15. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. In STOC 2014 Proc., pages 89-98. ACM, 2014. URL: http://dx.doi.org/10.1145/2591796.2591851.
  16. 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.
  17. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1727.
  18. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  19. 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.
  20. Takumi Kasai, Akeo Adachi, and Shigeki Iwata. Classes of pebble games and complete problems. SIAM Journal on Computing, 8(4):574-586, 1979. URL: http://dx.doi.org/10.1137/0208046.
  21. Donald Erwin Knuth. The Art of Computer Programming, volume 3 / Sorting and Searching. Addison-Wesley, 1982. ISBN 0-201-03803-X. Google Scholar
  22. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS, 105:41-72, 2011. URL: http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/96.
  23. Dániel Marx. Can you beat treewidth? Theory of Computing, 6(1):85-112, 2010. URL: http://dx.doi.org/10.4086/toc.2010.v006a005.
  24. Dániel Marx and Michal Pilipczuk. Optimal parameterized algorithms for planar facility location problems using voronoi diagrams. CoRR, abs/1504.05476, 2015. URL: http://arxiv.org/abs/1504.05476.
  25. Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno. Approximation and hardness of token swapping. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 66:1-66:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.66.
  26. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-27875-4.
  27. Igor Pak. Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ARY trees. Disc. Math., 204(1):329-335, 1999. URL: http://dx.doi.org/10.1016/S0012-365X(98)00377-X.
  28. Torrence D Parsons. Pursuit-evasion in a graph. In Theory and applications of graphs, pages 426-441. Springer, 1978. Google Scholar
  29. Walter J. Savitch. Relationships Between Nondeterministic and Deterministic Tape Complexities. J. Comput. Syst. Sci., 4(2):177-192, 1970. URL: http://dx.doi.org/10.1016/S0022-0000(70)80006-X.
  30. 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.
  31. 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. In FUN 2014 Proc., pages 364-375. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-07890-8_31.
  32. Katsuhisa Yamanaka, Takashi Horiyama, David G. Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, and Yushi Uno. Swapping colored tokens on graphs. In WADS 2015 Proc., pages 619-628, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21840-3_51.
  33. 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