{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T20:25:45Z","timestamp":1776284745243,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,5,10]],"date-time":"2016-05-10T00:00:00Z","timestamp":1462838400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,5]]},"DOI":"10.1007\/s00453-016-0159-2","type":"journal-article","created":{"date-parts":[[2016,5,10]],"date-time":"2016-05-10T14:01:37Z","timestamp":1462888897000},"page":"274-297","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":44,"title":["On the Parameterized Complexity of Reconfiguration Problems"],"prefix":"10.1007","volume":"78","author":[{"given":"Amer E.","family":"Mouawad","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naomi","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Narges","family":"Simjour","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akira","family":"Suzuki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,10]]},"reference":[{"key":"159_CR1","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., Gutin, G.: Digraphs: theory, algorithms and applications. In: Springer Monographs in Mathematics. Springer-Verlag, London (2008)","DOI":"10.1007\/978-1-84800-998-1"},{"key":"159_CR2","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: A cubic kernel for feedback vertex set. In: Proceedings of the 24th Annual Conference on Theoretical Aspects of Computer Science, pp. 320\u2013331 (2007)","DOI":"10.1007\/978-3-540-70918-3_28"},{"key":"159_CR3","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/j.endm.2013.10.040","volume":"44","author":"M Bonamy","year":"2013","unstructured":"Bonamy, M., Bousquet, N.: Recoloring bounded treewidth graphs. Electron. Notes Discrete Math. 44, 257\u2013262 (2013)","journal-title":"Electron. Notes Discrete Math."},{"key":"159_CR4","doi-asserted-by":"crossref","unstructured":"Bonsma, P.: The complexity of rerouting shortest paths. In: Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, pp. 222\u2013233 (2012)","DOI":"10.1007\/978-3-642-32589-2_22"},{"issue":"50","key":"159_CR5","doi-asserted-by":"crossref","first-page":"5215","DOI":"10.1016\/j.tcs.2009.08.023","volume":"410","author":"P Bonsma","year":"2009","unstructured":"Bonsma, P., Cereceda, L.: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theor. Comput. Sci. 410(50), 5215\u20135226 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"159_CR6","doi-asserted-by":"crossref","unstructured":"Bonsma, P., Mouawad, A.E., Nishimura, N., Raman, V.: The complexity of bounded length graph recoloring and CSP reconfiguration. In: Proceedings of the 9th International Symposium on Parameterized and Exact Computation, pp. 110\u2013121 (2014)","DOI":"10.1007\/978-3-319-13524-3_10"},{"key":"159_CR7","unstructured":"Cereceda, L.: Mixing graph colourings. Ph.D. thesis, London School of Economics (2007)"},{"issue":"7","key":"159_CR8","doi-asserted-by":"crossref","first-page":"1593","DOI":"10.1016\/j.ejc.2009.03.011","volume":"30","author":"L Cereceda","year":"2009","unstructured":"Cereceda, L., van den Heuvel, J., Johnson, M.: Mixing 3-colourings in bipartite graphs. Eur. J. Comb. 30(7), 1593\u20131606 (2009)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"159_CR9","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/jgt.20514","volume":"67","author":"L Cereceda","year":"2011","unstructured":"Cereceda, L., van den Heuvel, J., Johnson, M.: Finding paths between 3-colorings. J. Graph Theory 67(1), 69\u201382 (2011)","journal-title":"J. Graph Theory"},{"key":"159_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015). doi: 10.1007\/978-3-319-21275-3"},{"issue":"4","key":"159_CR11","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/j.jda.2009.01.003","volume":"7","author":"P Damaschke","year":"2009","unstructured":"Damaschke, P., Molokov, L.: The union of minimal hitting sets: parameterized combinatorial bounds and counting. J. Discrete Algorithms 7(4), 391\u2013401 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"159_CR12","volume-title":"Graph Theory","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Springer, Berlin (2005). (Electronic Edition)"},{"key":"159_CR13","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1997","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1997)"},{"issue":"3","key":"159_CR14","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1016\/j.jcss.2011.10.003","volume":"78","author":"MR Fellows","year":"2012","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Villanger, Y.: Local search: is brute-force avoidable? J. Comput. Syst. Sci. 78(3), 707\u2013719 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"159_CR15","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"issue":"6","key":"159_CR16","doi-asserted-by":"crossref","first-page":"2330","DOI":"10.1137\/07070440X","volume":"38","author":"P Gopalan","year":"2009","unstructured":"Gopalan, P., Kolaitis, P.G., Maneva, E.N., Papadimitriou, C.H.: The connectivity of Boolean satisfiability: computational and structural dichotomies. SIAM J. Comput. 38(6), 2330\u20132355 (2009)","journal-title":"SIAM J. Comput."},{"issue":"8","key":"159_CR17","doi-asserted-by":"crossref","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J Guo","year":"2006","unstructured":"Guo, J., Gramm, J., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386\u20131396 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"159_CR18","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1007\/s00373-013-1302-3","volume":"30","author":"R Haas","year":"2014","unstructured":"Haas, R., Seyffarth, K.: The $$k$$ k -dominating graph. Graphs Comb. 30(3), 609\u2013617 (2014)","journal-title":"Graphs Comb."},{"key":"159_CR19","doi-asserted-by":"crossref","unstructured":"Haddadan, A., Ito, T., Mouawad, A.E., Nishimura, N., Ono, H., Suzuki, A., Tebbal, Y.: The complexity of dominating set reconfiguration. In: Proceedings of the 14th Algorithms and Data Structures Symposium (to appear) (2015)","DOI":"10.1007\/978-3-319-21840-3_33"},{"issue":"1\u20132","key":"159_CR20","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.tcs.2005.05.008","volume":"343","author":"RA Hearn","year":"2005","unstructured":"Hearn, R.A., Demaine, E.D.: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theor. Comput. Sci. 343(1\u20132), 72\u201396 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"159_CR21","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R.: The complexity of k-SAT. In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, pp. 237\u2013240 (1999)","DOI":"10.1109\/CCC.1999.766282"},{"issue":"4","key":"159_CR22","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"12\u201314","key":"159_CR23","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"T Ito","year":"2011","unstructured":"Ito, T., Demaine, E.D., Harvey, N.J.A., Papadimitriou, C.H., Sideri, M., Uehara, R., Uno, Y.: On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12\u201314), 1054\u20131065 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"15","key":"159_CR24","doi-asserted-by":"crossref","first-page":"2199","DOI":"10.1016\/j.dam.2012.05.014","volume":"160","author":"T Ito","year":"2012","unstructured":"Ito, T., Kami\u0144ski, M., Demaine, E.D.: Reconfiguration of list edge-colorings in a graph. Discrete Appl. Math. 160(15), 2199\u20132207 (2012)","journal-title":"Discrete Appl. Math."},{"key":"159_CR25","doi-asserted-by":"crossref","unstructured":"Ito, T., Kami\u0144ski, M., Ono, H.: Fixed-parameter tractability of token jumping on planar graphs. In: Algorithms and Computation, Lecture Notes in Computer Science, Springer International Publishing, pp. 208\u2013219 (2014)","DOI":"10.1007\/978-3-319-13075-0_17"},{"key":"159_CR26","doi-asserted-by":"crossref","unstructured":"Ito, T., Kami\u0144ski, M., Ono, H., Suzuki, A., Uehara, R., Yamanaka, K.: On the parameterized complexity for token jumping on graphs. In: Proceedings of the 11th Annual Conference on Theory and Applications of Models of Computation. Lecture Notes in Computer Science, vol. 8402, pp. 341\u2013351. Springer International Publishing (2014)","DOI":"10.1007\/978-3-319-06089-7_24"},{"key":"159_CR27","doi-asserted-by":"crossref","unstructured":"Johnson, M., Kratsch, D., Kratsch, S., Patel, V., Paulusma, D.: Finding shortest paths between graph colourings. In: Proceedings of the 9th International Symposium on Parameterized and Exact Computation, pp. 221\u2013233 (2014)","DOI":"10.1007\/978-3-319-13524-3_19"},{"issue":"39","key":"159_CR28","doi-asserted-by":"crossref","first-page":"5205","DOI":"10.1016\/j.tcs.2011.05.021","volume":"412","author":"M Kami\u0144ski","year":"2011","unstructured":"Kami\u0144ski, M., Medvedev, P., Milani\u010d, M.: Shortest paths between shortest paths. Theor. Comput. Sci. 412(39), 5205\u20135210 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"159_CR29","doi-asserted-by":"crossref","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci. 289(2), 997\u20131008 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"159_CR30","first-page":"4:1","volume":"7","author":"S Kratsch","year":"2014","unstructured":"Kratsch, S., Pilipczuk, M., Rai, A., Raman, V.: Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs. Trans. Comput. Theory 7(1), 4:1\u20134:18 (2014)","journal-title":"Trans. Comput. Theory"},{"issue":"2","key":"159_CR31","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"159_CR32","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Mouawad, A.E., Panolan, F., Ramanujan, M., Saurabh, S.: Reconfiguration on sparse graphs. In: Proceedings of the Algorithms and Data Structures Symposium (to appear) (2015)","DOI":"10.1007\/978-3-319-21840-3_42"},{"key":"159_CR33","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2013.07.019","volume":"506","author":"N Misra","year":"2013","unstructured":"Misra, N., Narayanaswamy, N., Raman, V., Shankar, B.S.: Solving min ones 2-SAT as fast as vertex cover. Theor. Comput. Sci. 506, 115\u2013121 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"159_CR34","doi-asserted-by":"crossref","unstructured":"Mouawad, A.E., Nishimura, N., Pathak, V., Raman, V.: Shortest reconfiguration paths in the solution space of Boolean formulas. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, vol. 9134, pp. 985\u2013996 (2015)","DOI":"10.1007\/978-3-662-47672-7_80"},{"key":"159_CR35","doi-asserted-by":"crossref","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V.: Vertex cover reconfiguration and beyond. In: Proceedings of the 25th International Symposium on Algorithms and Computation, pp. 452\u2013463 (2014)","DOI":"10.1007\/978-3-319-13075-0_36"},{"key":"159_CR36","doi-asserted-by":"crossref","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V., Wrochna, M.: Reconfiguration over tree decompositions. In: Proceedings of the 9th International Symposium on Parameterized and Exact Computation, pp. 246\u2013257 (2014)","DOI":"10.1007\/978-3-319-13524-3_21"},{"key":"159_CR37","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"issue":"3","key":"159_CR38","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1016\/j.tcs.2005.10.010","volume":"351","author":"V Raman","year":"2006","unstructured":"Raman, V., Saurabh, S.: Parameterized algorithms for feedback set problems and their duals in tournaments. Theor. Comput. Sci. 351(3), 446\u2013458 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"159_CR39","doi-asserted-by":"crossref","unstructured":"Suzuki, A., Mouawad, A.E., Nishimura, N.: Reconfiguration of dominating sets. In: Proceedings of the 20th International Computing and Combinatorics Conference, pp. 405\u2013416 (2014)","DOI":"10.1007\/978-3-319-08783-2_35"},{"issue":"2","key":"159_CR40","doi-asserted-by":"crossref","first-page":"32:1","DOI":"10.1145\/1721837.1721848","volume":"6","author":"S Thomass\u00e9","year":"2010","unstructured":"Thomass\u00e9, S.: A $$4k^2$$ 4 k 2 kernel for feedback vertex set. ACM Trans. Algorithms 6(2), 32:1\u201332:8 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"159_CR41","first-page":"127","volume":"409","author":"J Heuvel van den","year":"2013","unstructured":"van den Heuvel, J.: The complexity of change. Surv. Comb. 409, 127\u2013160 (2013)","journal-title":"Surv. Comb."},{"key":"159_CR42","unstructured":"Wrochna, M.: Reconfiguration in bounded bandwidth and treedepth. CoRR (2014). ArXiv:1405.0847"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0159-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0159-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0159-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0159-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,7]],"date-time":"2019-09-07T13:41:49Z","timestamp":1567863709000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0159-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,10]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["159"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0159-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,10]]}}}