{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T20:26:07Z","timestamp":1776284767732,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,10,30]],"date-time":"2018-10-30T00:00:00Z","timestamp":1540857600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"<jats:p>\n            We settle the complexity of the I\n            <jats:sc>ndependent<\/jats:sc>\n            S\n            <jats:sc>et<\/jats:sc>\n            R\n            <jats:sc>econfiguration<\/jats:sc>\n            problem on bipartite graphs under all three commonly studied reconfiguration models. We show that under the token jumping or token addition\/removal model, the problem is NP-complete. For the token sliding model, we show that the problem remains PSPACE-complete.\n          <\/jats:p>","DOI":"10.1145\/3280825","type":"journal-article","created":{"date-parts":[[2018,10,30]],"date-time":"2018-10-30T12:11:00Z","timestamp":1540901460000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["The Complexity of Independent Set Reconfiguration on Bipartite Graphs"],"prefix":"10.1145","volume":"15","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amer E.","family":"Mouawad","sequence":"additional","affiliation":[{"name":"American University of Beirut, Lebanon"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,10,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1328-0"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"A tourist guide through treewidth","volume":"11","author":"Bodlaender Hans L.","year":"1993","journal-title":"Acta Cybern."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00031-0"},{"key":"e_1_2_1_5_1","unstructured":"Marthe Bonamy and Nicolas Bousquet. 2016. Token sliding on chordal graphs. CoRR abs\/1605.00442 (2016). DOI:http:\/\/arxiv.org\/abs\/1605.00442  Marthe Bonamy and Nicolas Bousquet. 2016. Token sliding on chordal graphs. CoRR abs\/1605.00442 (2016). DOI:http:\/\/arxiv.org\/abs\/1605.00442"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08404-6_8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.05.015"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.07.028"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Marek Cygan Fedor V. Fomin Lukasz Kowalik Daniel Lokshtanov D\u00e1niel Marx Marcin Pilipczuk Michal Pilipczuk and Saket Saurabh. 2015. Parameterized Algorithms. Springer.   Marek Cygan Fedor V. Fomin Lukasz Kowalik Daniel Lokshtanov D\u00e1niel Marx Marcin Pilipczuk Michal Pilipczuk and Saket Saurabh. 2015. Parameterized Algorithms. Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13075-0_31"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Erik D. Demaine and Joseph O\u2019Rourke. 2007. Geometric Folding Algorithms\u2014Linkages Origami Polyhedra. Cambridge University Press.   Erik D. Demaine and Joseph O\u2019Rourke. 2007. Geometric Folding Algorithms\u2014Linkages Origami Polyhedra. Cambridge University Press.","DOI":"10.1017\/CBO9780511735172"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48971-0_21"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_50"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/07070440X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01462229"},{"key":"e_1_2_1_16_1","volume-title":"Classic Papers in Combinatorics","author":"Hall Philip"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.05.008"},{"key":"e_1_2_1_18_1","unstructured":"Duc A. Hoang and Ryuhei Uehara. 2016. Sliding tokens on a cactus. Retrieved from https:\/\/hoanganhduc.github.io\/events\/ISAAC2016\/slide.pdf. {ISAAC Presentation slides}.  Duc A. Hoang and Ryuhei Uehara. 2016. Sliding tokens on a cactus. Retrieved from https:\/\/hoanganhduc.github.io\/events\/ISAAC2016\/slide.pdf. {ISAAC Presentation slides}."},{"key":"e_1_2_1_19_1","unstructured":"Duc A. Hoang and Ryuhei Uehara. 2017. Polynomial-time algorithms for sliding tokens on cactus graphs and block graphs. CoRR abs\/1705.00429 (2017). DOI:http:\/\/arxiv.org\/abs\/1705.00429  Duc A. Hoang and Ryuhei Uehara. 2017. Polynomial-time algorithms for sliding tokens on cactus graphs and block graphs. CoRR abs\/1705.00429 (2017). DOI:http:\/\/arxiv.org\/abs\/1705.00429"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.12.005"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2344966.2345127"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-06089-7_24"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Takehiro Ito Hiroyuki Nooka and Xiao Zhou. 2016. Reconfiguration of vertex covers in a graph. IEICE Transactions 99-D 3 (2016) 598--606.  Takehiro Ito Hiroyuki Nooka and Xiao Zhou. 2016. Reconfiguration of vertex covers in a graph. IEICE Transactions 99-D 3 (2016) 598--606.","DOI":"10.1587\/transinf.2015FCP0010"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.2307\/2369492"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.004"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS\u201915)","author":"Iyad"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.3233\/ICG-2008-31103"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21840-3_42"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2014.11.001"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_80"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13075-0_36"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0159-2"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1027"},{"key":"e_1_2_1_35_1","first-page":"127","article-title":"The complexity of change","volume":"2013","author":"van den Heuvel Jan","year":"2013","journal-title":"Surveys in Combinatorics"},{"key":"e_1_2_1_36_1","unstructured":"Marcin Wrochna. 2014. Reconfiguration in bounded bandwidth and treedepth. CoRR abs\/1405.0847 (2014). DOI:http:\/\/arxiv.org\/abs\/1405.0847  Marcin Wrochna. 2014. Reconfiguration in bounded bandwidth and treedepth. CoRR abs\/1405.0847 (2014). DOI:http:\/\/arxiv.org\/abs\/1405.0847"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS\u201915)","author":"Wrochna Marcin","year":"2015"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3280825","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3280825","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:01:51Z","timestamp":1750208511000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3280825"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,30]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3280825"],"URL":"https:\/\/doi.org\/10.1145\/3280825","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,30]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}