# Vertex Cover Reconfiguration and Beyond +
## 6 FPT Algorithms
### FPT Algorithm for Graphs of Bounded Degree
As we have obtained a contradiction, we can conclude that when \(\chi\) is successful, \(V(\sigma)\) can intersect at most \(\ell\) connected components of \(G[V_{\mathcal{R}}]\), and none of those components can be of a size greater than \(\ell\), as claimed. Given Proposition 10, we can safely assume that every connected component of \(G[V_{\mathcal{R}}]\) consists of at most \(\ell\) vertices (as the remaining components can be ignored when \(\chi\) is successful). For simplicity, let us first assume that \(G[V(\sigma)]\) is connected. Thus, if \(\chi\) is successful, then there exists a single component in \(G[V_{\mathcal{R}}]\), say \(C^{\star}\), such that \(V(\sigma)\subseteq V(C^{\star})\), \(|V(C^{\star})|\leq\ell\) and \(S_{R}\cup T_{A}\subseteq V(C^{\star})\). Therefore, we can simply enumerate all possible sequences of length at most \(\ell\) and make sure that at least one of them is the required reconfiguration sequence from \(S\) to \(T\). This brute-force testing can be accomplished in time \(2^{\mathcal{O}(\ell\log\ell)}\cdot n^{\mathcal{O}(1)}\). Let us now consider the general case when \(G[V(\sigma)]\) is not necessarily connected. We say a component \(C\) of \(G[V_{\mathcal{R}}]\) is important if \(V(C)\cap(S_{R}\cup T_{A})\
eq\emptyset\). There are at most \(\ell\) important components. Hence, we only need to bound the number of unimportant components. To that end, we partition the unimportant components of \(G[V_{\mathcal{R}}]\) into equivalence classes with respect to the following relation \(\simeq\):  
\[C\simeq C^{\prime}\quad\Leftrightarrow\quad C\text{ is isomorphic to }C^{\prime}.\]  
**Proposition 11**. : _The total number of graphs with at most \(\ell\) vertices is at most \(2^{\mathcal{O}(\ell^{2})}\), and therefore, the equivalence relation \(\simeq\) has at most \(2^{\mathcal{O}(\ell^{2})}\) equivalence classes._  
Assume that some equivalence class contains more than \(\ell\) unimportant components. We claim that retaining only \(\ell\) of them is enough. To see why, it is enough to note that \(V(\sigma)\) intersects with at most \(\ell\) of those components; they are all isomorphic; and the neighbours of any such component are contained in \(C_{ST}\). Putting it all together, we know that we have at most \(2^{\mathcal{O}(\ell^{2})}\) equivalence classes, each with at most \(\ell\) components, and each component is of size at most \(\ell\). Hence, we can guess the sequence from \(S\) to \(T\) in time \(2^{\mathcal{O}(\ell^{3}\log\ell)}\cdot n^{\mathcal{O}(1)}\) (testing whether two graphs with \(\ell\) vertices are isomorphic can be accomplished naively in time \(2^{\ell\log\ell}\)). We have proven that the probability that \(\chi\) is successful is at least \(2^{-(\ell+1)d}\). Hence, to obtain a Monte Carlo algorithm with false negatives, we repeat the above procedure \(2^{(\ell+1)d}\) times and obtain the following result:  
**Theorem 6**. : _There exists a one-sided error Monte Carlo algorithm with false negatives that solves the vertex cover reconfiguration problem on graphs of degree at most \(d\) in time \(2^{(\ell+1)d}\cdot 2^{\mathcal{O}(\ell^{3}\log\ell)}\cdot n^{\mathcal{O}(1)}\)._