# Vertex Cover Reconfiguration and Beyond +
## 1 Introduction  
Under the reconfiguration framework, we consider structural and algorithmic questions related to the solution space of a search problem \(\mathcal{Q}\). Given an instance \(\mathcal{I}\), an optional range \([r_{l},r_{u}]\) bounding a numerically-quantifiable property \(\Psi\) of feasible solutions for \(\mathcal{Q}\) and a symmetric adjacency relation (usually polynomially-testable) \(\mathcal{A}\) on the set of feasible solutions, we can construct a reconfiguration graph \(\mathcal{R}_{\mathcal{Q}}(\mathcal{I},r_{l},r_{u})\) for each instance \(\mathcal{I}\) of \(\mathcal{Q}\). The nodes of \(\mathcal{R}_{\mathcal{Q}}(\mathcal{I},r_{l},r_{u})\) correspond to the feasible solutions of \(\mathcal{I}\) having \(r_{l}\leq\Psi\leq r_{u}\), and there is an edge between two nodes whenever the corresponding solutions are adjacent under \(\mathcal{A}\). An edge can be seen as a reconfiguration step transforming one solution into the other. Given two feasible solutions for \(\mathcal{I}\), \(S\) and \(T\), one can ask if there exists a walk (reconfiguration sequence) in \(\mathcal{R}_{\mathcal{Q}}(\mathcal{I},r_{l},r_{u})\) from \(S\) to \(T\), or for the shortest such walk. On the structural side, one can ask about the diameter of reconfiguration graph \(\mathcal{R}_{\mathcal{Q}}(\mathcal{I},r_{l},r_{u})\) or whether it is connected with respect to some or any \(\mathcal{I}\), fixed \(\mathcal{A}\) and fixed \(\Psi\). These types of reconfiguration questions have received considerable attention in recent years [1; 2; 3; 4; 5] and are interesting for a variety of reasons. From an algorithmic standpoint, reconfiguration problems model dynamic situations in which we seek to transform a solution into a more desirable one, maintaining feasibility during the process. Reconfiguration also models questions of evolution; it can represent the evolution of a genotype where only individual mutations are allowed and all genotypes must satisfy a certain fitness threshold, i.e., be feasible. Moreover, the study of reconfiguration yields insights into the structure of the solution space of the underlying problem, crucial for the design of efficient algorithms. In fact, one of the initial motivations behind such questions was to studythe performance of heuristics [2] and random sampling methods [6], where connectivity and other properties of the solution space play a crucial role. Reconfiguration problems have been studied mainly under classical complexity assumptions, with most work devoted to determining the existence of a reconfiguration sequence between two given solutions. For most NP-complete problems, this question has been shown to be PSPACE-complete [3; 7; 8], while for some problems in P, the reconfiguration question could be either in P [3] or PSPACE-complete [9]. As PSPACE-completeness implies that the number of vertices in reconfiguration graphs, and therefore the length of reconfiguration sequences, can be superpolynomial in the number of vertices in the input graph, it is natural to ask whether we can achieve tractability if we restrict the length of the sequence or other properties of the problem to a fixed constant. These results motivated [PERSON] et al. [10] to study reconfiguration under the parameterized complexity framework [11; 12]. The Vertex Cover Reconfiguration (VCR) problem was shown to be fixed-parameter tractable when parameterized by \(k\) and W[1]-hard when parameterized by \(\ell\)[10]; in \(\mathcal{R}_{\mathsf{VCR}}(G,0,k)\), each feasible solution for instance \(G\) is a vertex cover of size at most \(k\) (a subset \(S\subseteq V(G)\) such that each edge of the graph has at least one endpoint in \(S\)) and two solutions are adjacent if one can be obtained from the other by the addition or removal of a single vertex of \(G\). Motivated by these results, we embark on a systematic investigation of the parameterized complexity of the problem restricted to various graph classes.