Vertex cover reconfiguration and beyond

Abstract. In the Vertex Cover Reconfiguration (VCR) problem, given graph G = (V,E), positive integers k and `, and two vertex cov-ers 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 ` vertex additions or re-movals such that each operation results in a vertex cover of size at most k. Motivated by recent results establishing the W[1]-hardness of VCR when parameterized by `, we delineate the complexity of the problem restricted to various graph classes. In particular, we show that VCR re-mains W[1]-hard on bipartite graphs, is NP-hard but fixed-parameter tractable on graphs of bounded degree, and is solvable in time polyno-mial in |V (G) | on even-hole-free graphs and cactus graphs. We prove W[1]-hardness and fixed-parameter tractability via two new problems of independent interest.