**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”,
*Theoretical Computer Science*, volume 600, 2015, pages 132–142. **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 thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time; (2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between*I*_{b}and*I*_{r}whose length (i.e., the number of token-slides) is quadratic; and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length. **Comments**:- This paper is also available from ScienceDirect.
**Availability**:- The paper is available in PDF (584k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- TokenReconfigurationTrees_ISAAC2014 (Linear-time algorithm for sliding tokens on trees)

See also other papers by Erik Demaine.

Last updated January 15, 2021 by Erik Demaine.