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., & Yamada, T. In Ahn, H. & Shin, C., editors, Algorithms and Computation - ISAAC 2014, volume 8889, of Lecture Notes in Computer Science, pages 389--400. Springer International Publishing, 2014. ![Polynomial-time algorithm for sliding tokens on trees [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper ![Polynomial-time algorithm for sliding tokens on trees [pdf]](https://bibbase.org/img/filetypes/pdf.svg "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
{"_id":"Q5CkTSPvF8aoMsGPJ","authorIDs":[],"author_short":["Demaine, E.<nbsp>D.","Demaine, M.<nbsp>L.","Fox-Epstein, E.","Hoang, D.<nbsp>A.","Ito, T.","Ono, H.","Otachi, Y.","Uehara, R.","Yamada, T."],"bibbaseid":"demaine-demaine-foxepstein-hoang-ito-ono-otachi-uehara-yamada-polynomialtimealgorithmforslidingtokensontrees-2014","bibdata":{"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>","author":["Demaine, Erik D.","Demaine, Martin L.","Fox-Epstein, Eli","Hoang, Duc A.","Ito, Takehiro","Ono, Hirotaka","Otachi, Yota","Uehara, Ryuhei","Yamada, Takeshi"],"author_short":["Demaine, E.<nbsp>D.","Demaine, M.<nbsp>L.","Fox-Epstein, E.","Hoang, D.<nbsp>A.","Ito, T.","Ono, H.","Otachi, Y.","Uehara, R.","Yamada, T."],"bibtex":"@incollection{ Demaine2014poly,\n 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},\n editor = {Ahn, Hee-Kap and Chan-Su Shin},\n title = {Polynomial-time algorithm for sliding tokens on trees},\n booktitle = {Algorithms and Computation - {ISAAC 2014}},\n series = {Lecture Notes in Computer Science},\n publisher = {Springer International Publishing},\n year = {2014},\n pages = {389--400},\n volume = {8889},\n 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>},\n url = {http://link.springer.com/chapter/10.1007%2F978-3-319-13075-0_31},\n url_paper = {publications/10.10072F978-3-319-13075-0_31.pdf},\n doi = {10.1007/978-3-319-13075-0_31}\n}","bibtype":"incollection","booktitle":"Algorithms and Computation - ISAAC 2014","doi":"10.1007/978-3-319-13075-0_31","editor":["Ahn, Hee-Kap","Shin, Chan-Su"],"editor_short":["Ahn, H.","Shin, C."],"id":"Demaine2014poly","key":"Demaine2014poly","pages":"389--400","publisher":"Springer International Publishing","series":"Lecture Notes in Computer Science","title":"Polynomial-time algorithm for sliding tokens on trees","type":"incollection","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","volume":"8889","year":"2014","bibbaseid":"demaine-demaine-foxepstein-hoang-ito-ono-otachi-uehara-yamada-polynomialtimealgorithmforslidingtokensontrees-2014","role":"author","urls":{"Paper":"http://link.springer.com/chapter/10.1007%2F978-3-319-13075-0_31"," paper":"http://hoanganhduc.info/publications/10.10072F978-3-319-13075-0_31.pdf"},"downloads":0,"html":""},"bibtype":"incollection","biburl":"http://hoanganhduc.info/publications.bib","creationDate":"2015-02-14T09:18:44.367Z","downloads":0,"keywords":["dblp"],"search_terms":["polynomial","time","algorithm","sliding","tokens","trees","demaine","demaine","fox-epstein","hoang","ito","ono","otachi","uehara","yamada"],"title":"Polynomial-time algorithm for sliding tokens on trees","year":2014,"dataSources":["vqv5tFwHyL63cuE3q"]}