Linear-Time Algorithm for Sliding Tokens on Trees
Suppose that we are given two independent sets I [subscript b] and I [subscript r] of a graph such that ∣ I [subscript b] ∣ = ∣ I [subscript r] ∣, and imagine that a token is placed on each vertex in I [subscript b]. Then, the sliding token problem is to determine whether there exists a sequence of...
| Main Authors: | , , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99985 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826188118192029696 |
|---|---|
| author | Demaine, Erik D. Demaine, Martin L. Fox-Epstein, Eli Hoang, Duc A. Ito, Takehiro Ono, Hirotaka Otachi, Yota Uehara, Ryuhei Yamada, Takeshi |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D. Demaine, Martin L. Fox-Epstein, Eli Hoang, Duc A. Ito, Takehiro Ono, Hirotaka Otachi, Yota Uehara, Ryuhei Yamada, Takeshi |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | Suppose that we are given two independent sets I [subscript b] and I [subscript r] of a graph such that ∣ I [subscript b] ∣ = ∣ I [subscript r] ∣, and imagine that a token is placed on each vertex in I [subscript b]. Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms I [subscript b] and I [subscript 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 [subscript b] and I [subscript 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. |
| first_indexed | 2024-09-23T07:54:52Z |
| format | Article |
| id | mit-1721.1/99985 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T07:54:52Z |
| publishDate | 2015 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/999852022-09-23T09:33:51Z Linear-Time Algorithm for Sliding Tokens on Trees Polynomial-Time Algorithm for Sliding Tokens on Trees Demaine, Erik D. Demaine, Martin L. Fox-Epstein, Eli Hoang, Duc A. Ito, Takehiro Ono, Hirotaka Otachi, Yota Uehara, Ryuhei Yamada, Takeshi Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Demaine, Martin L. Suppose that we are given two independent sets I [subscript b] and I [subscript r] of a graph such that ∣ I [subscript b] ∣ = ∣ I [subscript r] ∣, and imagine that a token is placed on each vertex in I [subscript b]. Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms I [subscript b] and I [subscript 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 [subscript b] and I [subscript 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. National Science Foundation (U.S.) (Grant CCF-1161626) United States. Defense Advanced Research Projects Agency (United States. Air Force Office of Scientific Research Grant FA9550-12-1-0423) 2015-11-23T14:48:03Z 2015-11-23T14:48:03Z 2014 Article http://purl.org/eprint/type/ConferencePaper 978-3-319-13074-3 978-3-319-13075-0 0302-9743 1611-3349 http://hdl.handle.net/1721.1/99985 Demaine, Erik D., Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada. “Polynomial-Time Algorithm for Sliding Tokens on Trees.” Lecture Notes in Computer Science (2014): 389–400. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1007/978-3-319-13075-0_31 Algorithms and Computation Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Demaine, Erik D. Demaine, Martin L. Fox-Epstein, Eli Hoang, Duc A. Ito, Takehiro Ono, Hirotaka Otachi, Yota Uehara, Ryuhei Yamada, Takeshi Linear-Time Algorithm for Sliding Tokens on Trees |
| title | Linear-Time Algorithm for Sliding Tokens on Trees |
| title_full | Linear-Time Algorithm for Sliding Tokens on Trees |
| title_fullStr | Linear-Time Algorithm for Sliding Tokens on Trees |
| title_full_unstemmed | Linear-Time Algorithm for Sliding Tokens on Trees |
| title_short | Linear-Time Algorithm for Sliding Tokens on Trees |
| title_sort | linear time algorithm for sliding tokens on trees |
| url | http://hdl.handle.net/1721.1/99985 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT demaineerikd lineartimealgorithmforslidingtokensontrees AT demainemartinl lineartimealgorithmforslidingtokensontrees AT foxepsteineli lineartimealgorithmforslidingtokensontrees AT hoangduca lineartimealgorithmforslidingtokensontrees AT itotakehiro lineartimealgorithmforslidingtokensontrees AT onohirotaka lineartimealgorithmforslidingtokensontrees AT otachiyota lineartimealgorithmforslidingtokensontrees AT uehararyuhei lineartimealgorithmforslidingtokensontrees AT yamadatakeshi lineartimealgorithmforslidingtokensontrees AT demaineerikd polynomialtimealgorithmforslidingtokensontrees AT demainemartinl polynomialtimealgorithmforslidingtokensontrees AT foxepsteineli polynomialtimealgorithmforslidingtokensontrees AT hoangduca polynomialtimealgorithmforslidingtokensontrees AT itotakehiro polynomialtimealgorithmforslidingtokensontrees AT onohirotaka polynomialtimealgorithmforslidingtokensontrees AT otachiyota polynomialtimealgorithmforslidingtokensontrees AT uehararyuhei polynomialtimealgorithmforslidingtokensontrees AT yamadatakeshi polynomialtimealgorithmforslidingtokensontrees |