Polynomial-time algorithm for sliding tokens on trees

Polynomial-time algorithm for sliding tokens on trees. Demaine, E. D.; Demaine, M. L.; Fox-Epstein, E.; Hoang, D. A.; Ito, T.; Ono, H.; Otachi, Y.; Uehara, R.; and Yamada, T. In Ahn, H. and Shin, C., editors, Algorithms and Computation - ISAAC 2014, volume 8889, of Lecture Notes in Computer Science, pages 389--400. Springer International Publishing, 2014.

Paper

Polynomial-time algorithm for sliding tokens on trees [pdf]

Paper doi abstract bibtex

Suppose that we are given two independent sets $I_b$ and $I_r$ of a graph such that $| I_b | = | I_r |$, 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$ into $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.

@incollection{ Demaine2014poly,
  author = {Demaine, Erik D. and Demaine, Martin L. and Fox-Epstein, Eli and Hoang, Duc A. and Ito, Takehiro and Ono, Hirotaka and Otachi, Yota and Uehara, Ryuhei and Yamada, Takeshi},
  editor = {Ahn, Hee-Kap and Chan-Su Shin},
  title = {Polynomial-time algorithm for sliding tokens on trees},
  booktitle = {Algorithms and Computation - {ISAAC 2014}},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer International Publishing},
  year = {2014},
  pages = {389--400},
  volume = {8889},
  abstract = {<p> Suppose that we are given two independent sets $I_b$ and $I_r$ of a graph such that $| I_b | = | I_r |$, 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$ into $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. </p>},
  url = {http://link.springer.com/chapter/10.1007%2F978-3-319-13075-0_31},
  url_paper = {publications/10.10072F978-3-319-13075-0_31.pdf},
  doi = {10.1007/978-3-319-13075-0_31}
}

Downloads: 0