# Introduction to Reconfiguration
## 5 Parameterized Complexity (Independent Set and Vertex Cover)  
Parameterized complexity offers a way of distinguishing among intractable problems by identifying situations in which the running time is tied to one or more parameters of the problem or instance. A problem is _fixed-parameter tractable_ (or in the class _FPT_) if it can be solved in time \(f(p)n^{O(1)}\), for \(n\) the size of the input, \(p\) a _parameter_, and \(f\) a computable function [65]. A parameterized algorithm makes it possible to associate the non-polynomial part of the running time with a parameter. Problems that are intractable with respect to fixed-parameter complexity are \(W[\ell]\)-_hard_ for some \(\ell\geq 1\). Choosing the size of the solutions or a property of an instance (such as its treewidth or degree) as a parameter allows us to compare the parameterized complexity of reconfiguration with the parameterized complexity of the source problem. A further motivation for considering parameterized complexity follows from the observation that, in many cases, there appears to be a correlation between the diameter of the reconfiguration graph and the complexity of reachability. When polynomial diameter is associated with polynomial-time reachability algorithms and exponential diameter with PSPACE-completeness for reachability, it is natural to wonder whether the length of the shortest reconfiguration sequence (for which the diameter is an upper bound) plays a role in the complexity. Certainly, a bound on diameter implies a bound on the length of a reconfiguration sequence, which perhaps would imply a bound on the time to determine if one exists. This suggests that parameterizing by the length of the reconfiguration sequence might result in fixed-parameter algorithms for instances even when the diameter is not guaranteed to be polynomial. Prior to its use in reconfiguration, length was used to parameterize a problem by the number of moves in a solution to a puzzle (which can, in fact, be viewed as a reconfiguration sequence) [66]. With respect to classical complexity, results for Independent Set Reconfiguration and Vertex Cover Reconfiguration are interchangeable: we simply reinterpret the placement of tokens on vertices to indicate the subset of vertices not in the solution (recall that each edge has at least one endpoint in a vertex cover, so that the remaining vertices form an independent set). More precisely, for a given instance \(G\), the reconfiguration graphs for \(G\) for Independent Set and Vertex Cover will be isomorphic under TJ and TS, as well as under TAR when the bound on the size of solutions to one problem is \(k\) and the bound on the size of solutions to the other problem is \(|V(G)|-k\). The difference in the size of solutions required to translate between reconfiguration graphs of the two problems, while insignificant under classical complexity, reveals a more fundamental difference between the source problems with respect to fixed-parameter complexity. With respect to reachability there is a dividing line between the parameterized version of Independent Set, which is \(W[1]\)-hard, and Vertex Cover, which is in FPT, and is so amenable to algorithmic approaches that it has earned the moniker of \"Drosophila\" of fixed-parameter algorithmics [67]. Consequently, it would not be surprising to find a significant difference in the complexities of reachability for the two problems. The relationship between Independent Set and Vertex Cover can be characterized in terms of a _hereditary property_ (a property of a graph that is also a property of any of its induced subgraphs). The _subset problem for hereditary property_\(\pi\) is the problem of finding a subset \(V^{\prime}\) of the vertices such that the subgraph induced on \(V^{\prime}\) has property \(\pi\); thus, Independent Set is the subset problem for \(\pi\) being the absence of edges.