Polynomial-Time Algorithm for Sliding Tokens on Trees

详细信息    查看全文

• 作者：Erik D. Demaine (15)
  Martin L. Demaine (15)
  Eli Fox-Epstein (16)
  Duc A. Hoang (17)
  Takehiro Ito (18)
  Hirotaka Ono (19)
  Yota Otachi (17)
  Ryuhei Uehara (17)
  Takeshi Yamada (17)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：1
• 期：1
• 页码：389-400
• 全文大小：380 KB
• 参考文献：1. Bodlaender, H.L.: A partial \(k\) -arboretum of graphs with bounded treewidth. Theoretical Computer Science 209, 1鈥?5 (1998) CrossRef
  2. Bonamy, M., Johnson, M., Lignos, I., Patel, V., Paulusma, D.: Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. J. Combinatorial Optimization 27, 132鈥?43 (2014) CrossRef
  3. Bonsma, P.: The complexity of rerouting shortest paths. Theoretical Computer Science 510, 1鈥?2 (2013) CrossRef
  4. Bonsma, P.: Independent set reconfiguration in cographs. To appear in WG 2014, arXiv:1402.1587 (2014)
  5. Bonsma, P., Cereceda, L.: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoretical Computer Science 410, 5215鈥?226 (2009) CrossRef
  6. Bonsma, P., Kami艅ski, M., Wrochna, M.: Reconfiguring independent sets in claw-free graphs. In: Ravi, R., G酶rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 86鈥?7. Springer, Heidelberg (2014) CrossRef
  7. Demaine, E.D., Demaine, M.L., Fox-Epstein, E., Hoang, D.A., Ito, T., Ono, H., Otachi, Y., Uehara, R., Yamada, T.: Linear-time algorithm for sliding tokens on trees arXiv:1406.6576 (2014)
  8. Gopalan, P., Kolaitis, P.G., Maneva, E.N., Papadimitriou, C.H.: The connectivity of Boolean satisfiability: computational and structural dichotomies. SIAM J. Computing 38, 2330鈥?355 (2009) CrossRef
  9. Hearn, R.A., Demaine, E.D.: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science 343, 72鈥?6 (2005) CrossRef
  10. Hearn, R.A., Demaine, E.D.: Games, Puzzles, and Computation. A K Peters (2009)
  11. Ito, T., Demaine, E.D., Harvey, N.J.A., Papadimitriou, C.H., Sideri, M., Uehara, R., Uno, Y.: On the complexity of reconfiguration problems. Theoretical Computer Science 412, 1054鈥?065 (2011) CrossRef
  12. Ito, T., Kami艅ski, M., Ono, H., Suzuki, A., Uehara, R., Yamanaka, K.: On the parameterized complexity for token jumping on graphs. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds.) TAMC 2014. LNCS, vol. 8402, pp. 341鈥?51. Springer, Heidelberg (2014) CrossRef
  13. Ito, T., Kawamura, K., Ono, H., Zhou, X.: Reconfiguration of list \(L(2,1)\) -labelings in a graph. Theoretical Computer Science 544, 84鈥?7 (2014) CrossRef
  14. Kami艅ski, M., Medvedev, P., Milani膷, M.: Shortest paths between shortest paths. Theoretical Computer Science 412, 5205鈥?210 (2011) CrossRef
  15. Kami艅ski, M., Medvedev, M., Milani膷, M.: Complexity of independent set reconfigurability problems. Theoretical Computer Science 439, 9鈥?5 (2012) CrossRef
  16. Makino, K., Tamaki, S., Yamamoto, M.: An exact algorithm for the Boolean connectivity problem for \(k\) -CNF. Theoretical Computer Science 412, 4613鈥?618 (2011) CrossRef
  17. Mouawad, A.E., Nishimura, N., Raman, V., Simjour, N., Suzuki, A.: On the parameterized complexity of reconfiguration problems. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 281鈥?94. Springer, Heidelberg (2013) CrossRef
  18. Mouawad, A.E., Nishimura, N., Raman, V., Wrochna, M.: Reconfiguration over tree decompositions arXiv:1405.2447
  19. van den Heuvel, J.: The complexity of change. Surveys in Combinatorics 2013, London Mathematical Society Lecture Notes Series 409 (2013)
  20. Wrochna, M.: Reconfiguration in bounded bandwidth and treedepth arXiv:1405.0847 (2014)
  
• 作者单位：Erik D. Demaine (15)
  Martin L. Demaine (15)
  Eli Fox-Epstein (16)
  Duc A. Hoang (17)
  Takehiro Ito (18)
  Hirotaka Ono (19)
  Yota Otachi (17)
  Ryuhei Uehara (17)
  Takeshi Yamada (17)
  
  15. MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, USA
  16. Department of Computer Science, Brown University, Providence, USA
  17. School of Information Science, JAIST, Nomi, Japan
  18. Graduate School of Information Sciences, Tohoku University, Sendai, Japan
  19. Faculty of Economics, Kyushu University, Fukuoka, Japan
  
• ISSN：1611-3349

文摘

Suppose that we are given two independent sets I \(_{b}\) and I \(_{r}\) of a graph such that \(\mid \) \({{\varvec{I}}}_{b}\) \(\mid \) = \(\mid \) I \(_{r}\) \(\mid \) , and imagine that a token is placed on each vertex in I \(_{b}\) . Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms I \(_{b}\) and I \(_{r}\) so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we show that the problem is solvable for trees in quadratic time. Our proof is constructive: for a yes-instance, we can find an actual sequence of independent sets between I \(_{b}\) and I \(_{r}\) whose length (i.e., the number of token-slides) is quadratic. We note that there exists an infinite family of instances on paths for which any sequence requires quadratic length.