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} }