Abstract
The token swapping problem (TSP) and its colored version are reconfiguration problems on graphs. This paper is concerned with the complexity of the TSP and two new variants; namely parallel TSP and parallel colored TSP. For a given graph where each vertex has a unique token on it, the TSP requires to find a shortest way to modify a token placement into another by swapping tokens on adjacent vertices. In the colored version, vertices and tokens are colored and the goal is to relocate tokens so that each vertex has a token of the same color. Their parallel versions allow simultaneous swaps on non-incident edges in one step. We investigate the time complexity of several restricted cases of those problems and show when those problems become tractable and remain intractable.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
No salesman is traveling in this paper.
References
Bitton, D., DeWitt, D.J., Hsiao, D.K., Menon, J.: A taxonomy of parallel sorting. ACM Comput. Surv. 16(3), 287–318 (1984)
Bonnet, É., Miltzow, T., Rzążewski, P.: Complexity of Token Swapping and Its Variants. CoRR, abs/1607.07676 (2016)
Edmonds, J.: Paths, trees, and flowers. Canad. J. Math. 17, 449–467 (1965)
Even, S., Goldreich, O.: The minimum-length generator sequence problem is NP-hard. J. Algorithms 2(3), 311–313 (1981)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979)
Heath, L.S., Vergara, J.P.C.: Sorting by short swaps. J. Comput. Biol. 10(5), 775–789 (2003)
Jerrum, M.: The complexity of finding minimum-length generator sequences. Theor. Comput. Sci. 36, 265–289 (1985)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) The Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85–103. Springer, Heidelberg (1972)
Kawahara, J., Saitoh, T., Yoshinaka, R.: A note on the complexity of the token swapping problem. IPSJ SIG Technical report, 2015-AL-156(3), 1–7 January 2016 (in Japanese)
Kawahara, J., Saitoh, T., Yoshinaka, R.: The time complexity of the token swapping problem and its parallel variants. CoRR, abs/1612.02948 (2016)
Miltzow, T., Narrins, L., Okamoto, Y., Rote, G., Thomas, A., Uno, T.: Approximation, hardness of token swapping. In: ESA, pp. 66:1–66:15 (2016)
Petersen, T.K., Tenner, B.E.; How to write a permutation as a product of involutions (and why you might care). Integers 13 (2013). Paper No. A63
Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci. 8, 189–201 (1979)
Yamanaka, K., Demaine, E.D., Ito, T., Kawahara, J., Kiyomi, M., Okamoto, Y., Saitoh, T., Suzuki, A., Uchizawa, K., Uno, T.: Swapping labeled tokens on graphs. In: Ferro, A., Luccio, F., Widmayer, P. (eds.) Fun with Algorithms. LNCS, vol. 8496, pp. 364–375. Springer, Heidelberg (2014). doi:10.1007/978-3-319-07890-8_31
Yamanaka, K., Horiyama, T., Kirkpatrick, D., Otachi, Y., Saitoh, T., Uehara, R., Uno, Y.: Swapping colored tokens on graphs. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 619–628. Springer, Heidelberg (2015). doi:10.1007/978-3-319-21840-3_51
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Kawahara, J., Saitoh, T., Yoshinaka, R. (2017). The Time Complexity of the Token Swapping Problem and Its Parallel Variants. In: Poon, SH., Rahman, M., Yen, HC. (eds) WALCOM: Algorithms and Computation. WALCOM 2017. Lecture Notes in Computer Science(), vol 10167. Springer, Cham. https://doi.org/10.1007/978-3-319-53925-6_35
Download citation
DOI: https://doi.org/10.1007/978-3-319-53925-6_35
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-53924-9
Online ISBN: 978-3-319-53925-6
eBook Packages: Computer ScienceComputer Science (R0)