{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:57:04Z","timestamp":1760241424277,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2018,2,9]],"date-time":"2018-02-09T00:00:00Z","timestamp":1518134400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["(No number)"],"award-info":[{"award-number":["(No number)"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In the Vertex Cover Reconfiguration (VCR) problem, given a graph G, positive integers k and \u2113 and two vertex covers S and T of G of size at most k, we determine whether S can be transformed into T by a sequence of at most \u2113 vertex additions or removals such that every operation results in a vertex cover of size at most k. Motivated by results establishing the     W [ 1 ]    -hardness of VCR when parameterized by \u2113, we delineate the complexity of the problem restricted to various graph classes. In particular, we show that VCR remains     W [ 1 ]    -hard on bipartite graphs, is    NP   -hard, but fixed-parameter tractable on (regular) graphs of bounded degree and more generally on nowhere dense graphs and is solvable in polynomial time on trees and (with some additional restrictions) on cactus graphs.<\/jats:p>","DOI":"10.3390\/a11020020","type":"journal-article","created":{"date-parts":[[2018,2,9]],"date-time":"2018-02-09T12:46:27Z","timestamp":1518180387000},"page":"20","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Vertex Cover Reconfiguration and Beyond"],"prefix":"10.3390","volume":"11","author":[{"given":"Amer","family":"Mouawad","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Bergen, PB 7803, N-5020 Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naomi","family":"Nishimura","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, Chennai 600113, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, 02-097 Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,2,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"517","DOI":"10.7151\/dmgt.1562","article-title":"\u03b3-Graphs of Graphs","volume":"31","author":"Fricke","year":"2011","journal-title":"Discuss. Math. Graph Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"2330","DOI":"10.1137\/07070440X","article-title":"The connectivity of boolean satisfiability: Computational and structural dichotomies","volume":"38","author":"Gopalan","year":"2009","journal-title":"SIAM J. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","article-title":"On the complexity of reconfiguration problems","volume":"412","author":"Ito","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Ito, T., Kawamura, K., Ono, H., and Zhou, X. (2012, January 19\u201321). Reconfiguration of list L(2, 1)-labelings in a graph. Proceedings of the 23rd Annual International Symposium on Algorithms and Computation, Taipei, Taiwan.","DOI":"10.1007\/978-3-642-35261-4_7"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"5205","DOI":"10.1016\/j.tcs.2011.05.021","article-title":"Shortest paths between shortest paths","volume":"412","author":"Medvedev","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1016\/j.disc.2007.07.028","article-title":"Connectedness of the graph of vertex-colourings","volume":"308","author":"Cereceda","year":"2008","journal-title":"Discret. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2199","DOI":"10.1016\/j.dam.2012.05.014","article-title":"Reconfiguration of list edge-colourings in a graph","volume":"160","author":"Ito","year":"2012","journal-title":"Discrete Appl. Math."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.tcs.2012.03.004","article-title":"Complexity of independent set reconfigurability problems","volume":"439","author":"Medvedev","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Bonsma, P. (2012, January 27\u201331). The complexity of rerouting shortest paths. Proceedings of the International Symposium on Mathematical Foundations of Computer Science, Bratislava, Slovakia.","DOI":"10.1007\/978-3-642-32589-2_22"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/s00453-016-0159-2","article-title":"On the Parameterized Complexity of Reconfiguration Problems","volume":"78","author":"Mouawad","year":"2017","journal-title":"Algorithmica"},{"key":"ref_11","unstructured":"Downey, R.G., and Fellows, M.R. (1997). Parameterized Complexity, Springer-Verlag."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (2013). Texts in Computer Science. Fundamentals of Parameterized Complexity, Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Mouawad, A.E., Nishimura, N., and Raman, V. (2014, January 15\u201317). Vertex Cover Reconfiguration and Beyond. Proceedings of the Algorithms and Computation\u201425th International Symposium, ISAAC 2014, Jeonju, Korea.","DOI":"10.1007\/978-3-319-13075-0_36"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2017.11.003","article-title":"Reconfiguration in bounded bandwidth and tree-depth","volume":"93","author":"Wrochna","year":"2018","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Diestel, R. (2005). Graph Theory, Springer-Verlag. Electronic Ed.","DOI":"10.4171\/owr\/2005\/03"},{"key":"ref_16","unstructured":"Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., and Symons, C.T. (2004, January 10). Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments. Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments, New Orleans, LA, USA."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Chor, B., Fellows, M.R., and Juedes, D. (2004, January 21\u201323). Linear Kernels in Linear Time, or How to Save k Colors in O(n2) Steps. Proceedings of the 30th International Conference on Graph-Theoretic Concepts in Computer Science, Bad Honnef, Germany.","DOI":"10.1007\/978-3-540-30559-0_22"},{"key":"ref_18","unstructured":"Hall, P. (1987). On Representatives of Subsets. Classic Papers in Combinatorics, Birkh\u00e4user Boston."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., and Spinrad, J.P. (1999). Graph Classes: A Survey, Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9780898719796"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1002\/jgt.10156","article-title":"Even cycles in graphs","volume":"45","author":"Conlon","year":"2004","journal-title":"J. Graph Theory"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1587\/transinf.2015FCP0010","article-title":"Reconfiguration of Vertex Covers in a Graph","volume":"99-D","author":"Ito","year":"2016","journal-title":"IEICE Trans."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","article-title":"Some Simplified NP-Complete Graph Problems","volume":"1","author":"Garey","year":"1976","journal-title":"Theor. Comput. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","article-title":"Color-coding","volume":"42","author":"Alon","year":"1995","journal-title":"J. ACM"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Cai, L., Chan, S.M., and Chan, S.O. (2006, January 13\u201315). Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems. Proceedings of the Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Z\u00fcrich, Switzerland.","DOI":"10.1007\/11847250_22"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Hodges, W. (1993). Model Theory, Cambridge University Press.","DOI":"10.1017\/CBO9780511551574"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1016\/j.ejc.2011.01.006","article-title":"On nowhere dense graphs","volume":"32","year":"2011","journal-title":"Euro. J. Comb."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., and De Mendez, P.O. (2012). Sparsity. Algorithms and Combinatorics, Springer.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/3051095","article-title":"Deciding first-order properties of nowhere dense graphs","volume":"64","author":"Grohe","year":"2017","journal-title":"J. ACM"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/2\/20\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:54:29Z","timestamp":1760194469000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/2\/20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,9]]},"references-count":29,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2018,2]]}},"alternative-id":["a11020020"],"URL":"https:\/\/doi.org\/10.3390\/a11020020","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,2,9]]}}}