# Introduction to Reconfiguration
## 5 Parameterized Complexity (Independent Set and Vertex Cover)
For any hereditary property \(\pi\), we can define reconfiguration in terms of either a set of vertices \(U\) of size at most \(k\) such that the subgraph induced on \(U\) has property \(\pi\) (\(\pi\)Subset Reconfiguration) or a set of vertices \(U\) of size at most \(k\) such that the subgraph induced on all vertices except those in \(U\) has property \(\pi\) (\(\pi\)Deletion Reconfiguration). For \(\pi\) the absence of edges, \(\pi\)Subset Reconfiguration is Independent Set Reconfiguration and \(\pi\)Deletion Reconfiguration is Vertex Cover Reconfiguration. General results have been found for hereditary properties that satisfy certain conditions, relating the complexity of \(\pi\)Subset Reconfiguration and \(\pi\)Deletion Reconfiguration under TAR to the complexity of the subset problem for \(\pi\). Determining if there is a reconfiguration sequence of length at most \(\ell\) for \(\pi\)Subset Reconfiguration parameterized by \(k+\ell\) or for \(\pi\)Deletion Reconfiguration parameterized by \(\ell\) is at least as hard as the source subset problem [68]. Subsequent work focused on connected hereditary properties, considering the reconfiguring of induced trees [69]. Due to the \(W[1]\)-hardness of Independent Set, reachability is \(W[1]\)-hard for Independent Set Reconfiguration parameterized by \(k+\ell\) and for Vertex Cover Reconfiguration parameterized by \(\ell\). Although this does not immediately imply a difference in the parameterized complexity of the two problems, further results, discussed later, do. One of the common algorithmic paradigms for fixed-parameter algorithms, _kernelization_, has been adapted to form a _reconfiguration kernel_, used to obtain fixed-parameter reachability algorithms for Bounded Hitting Set Reconfiguration, Vertex Cover Reconfiguration, and Feedback Vertex Set Reconfiguration under TAR, all parameterized by the solution size [70]. Although every problem in FPT can be shown to have a kernel, because kernels often represent only minimal or maximal solutions to the problem, whereas a reconfiguration sequence under TAR may make use of non-optimal solutions, the translation is not immediate [70]. In fact, it has been shown that there exists a source problem (Cluster Graph Reconfiguration) which, although in FPT when parameterized by \(k\), is \(W[1]\)-hard for reachability even when parameterized by both \(k\) and \(\ell\)[70] (a hardness result on multiple parameters immediately implies hardness on a smaller number of parameters). The results on Vertex Cover Reconfiguration and Independent Set Reconfiguration mentioned above indicate a difference in complexity when parameterized by the solution size, as the former is in FPT using a reconfiguration kernel and the latter is \(W[1]\)-hard using the general result on hereditary properties. Further work on Vertex Cover Reconfiguration has demonstrated that although it is \(W[1]\)-hard when parameterized by \(\ell\)[70] (by the general result on hereditary properties), it is in FPT when parameterized by \(\ell\) and the treewidth of the instance [49]. As Vertex Cover is fixed-parameter tractable on general graphs, one might imagine that the boundary between tractability and intractability of the source problem could predict the parameterized complexity of reachability on various graph classes, parameterized by \(\ell\). To the contrary, although Vertex Cover is NP-complete when restricted to planar graphs, reachability is in FPT parameterized by \(\ell\) for planar graphs [49] and graphs of degree at most \(d\), \(d\geq 4\)[54]. In contrast, despite the polynomial-time algorithm for Vertex Cover on bipartite graphs, reachability is \(W[1]\)-hard when parameterized by \(\ell\)[54]. The parameterized complexity of Independent Set Reconfiguration has been considered under both TS and TAR/TJ; as in the case of classical complexity, TAR and TJ are equivalent.