**Reference**:- 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”, in
*Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014)*, Lecture Notes in Computer Science, volume 8889, December 15–17, 2014, pages 389–400. **Abstract**:-
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. **Comments**:- This paper is also available from SpringerLink.
**Availability**:- The paper is available in PDF (240k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- TokenReconfigurationTrees_TCS2015 (Linear-time algorithm for sliding tokens on trees)

See also other papers by Erik Demaine.

Last updated July 21, 2021 by Erik Demaine.