# Vertex Cover Reconfiguration and Beyond +
## 6 FPT Algorithms
### FPT Algorithm for Graphs of Bounded Degree  
In this section, we prove that vertex cover reconfiguration parameterized by \(\ell\) is fixed-parameter tractable for graphs of degree at most \(d\). Our algorithm is randomized and based on a variant of the colour-coding technique [23] that is particularly useful in designing parameterized algorithms on graphs of bounded degree. The technique, known in the literature as random separation [24], boils down to a simple, but fruitful observation that in some cases, if we randomly colour the vertex set of a graph using two colours, the solution or vertices we are looking for are appropriately coloured with high probability. In our case, we want to make sure that the set of touched vertices gets highlighted. We note that our algorithm can easily be derandomized using standard techniques [25]. We start with an instance \((G,S,T,k,\ell)\) of VCR, with \(G\) having degree at most \(d\). Recall that we partition \(V(G)\) into the sets \(C_{ST}=S\cap T\), \(S_{R}=S\setminus C_{ST}\), \(T_{A}=T\setminus C_{ST}\), and the independent set \(O_{ST}=V(G)\setminus(S\cup T)=V(G)\setminus(C_{ST}\cup S_{R}\cup T_{A})\). We colour independently every vertex of \(G\) using one of two colours, say red and blue (denoted by \(\mathcal{R}\) and \(\mathcal{B}\)), with probability \(\frac{1}{2}\). We let \(\chi:V(G)\rightarrow\{\mathcal{R},\mathcal{B}\}\) denote the resulting random colouring. Suppose that \((G,S,T,k,\ell)\) is a yes-instance, and let \(\sigma\) denote a reconfiguration sequence from \(S\) to \(T\) of length at most \(\ell\). We say that the colouring \(\chi\) is successful if both of the following conditions hold:  
* Every vertex in \(V(\sigma)\) is coloured red; and
* Every vertex in \(N_{G}(V(\sigma))\) is coloured blue. Observe that \(V(\sigma)\) and \(N_{G}(V(\sigma))\) are disjoint. Therefore, the two aforementioned conditions are independent. Moreover, since the maximum degree of \(G\) is \(d\), we have \(|V(\sigma)|+|N_{G}(V(\sigma))|\leq(\ell+1)d\). Consequently, the probability that \(\chi\) is successful is at least:  
\[\frac{1}{2^{|V(\sigma)|+|N_{G}(V(\sigma))|}}\geq\frac{1}{2^{(\ell+1)d}}\enspace.\]  
Let \(V_{\mathcal{R}}\) denote the set of vertices coloured red and \(V_{\mathcal{B}}\) denote the set of vertices coloured blue. Moreover, we let \(C_{1}\),..., \(C_{q}\) denote the set of connected components of \(G[V_{\mathcal{R}}]\). The main observation now is the following:  
**Proposition 10**. : _If \(\chi\) is successful, then \(N_{G}(V(\sigma))\subseteq C_{ST}\), \(V(\sigma)\) has a non-empty intersection with at most \(\ell\) connected components of \(G[V_{\mathcal{R}}]\), and each one of those components consists of at most \(\ell\) vertices._  
Proof. : The fact that \(N_{G}(V(\sigma))\subseteq C_{ST}\) follows from the observation that every vertex in \(V(\sigma)\) must be added or removed at least once and no vertex in \(N_{G}(V(\sigma))\) is ever added or removed. In other words, if \(v\in V(\sigma)\) is removed, then all of its untouched neighbours must be in \(C_{ST}\). Similarly, if \(v\in V(\sigma)\) is added, then prior to being added, all of its untouched neighbours must be in \(C_{ST}\). Since \(|V(\sigma)|\leq\ell\), we know that \(G[V(\sigma)\cup N_{G}(V(\sigma))]\) consists of at most \(\ell\) connected components (each of size at most \((\ell+1)d\)) and \(G[V(\sigma)]\) consists of at most \(\ell\) components (each of size at most \(\ell\)). Let \(C\) be a connected component of \(G[V_{\mathcal{R}}]\) such that \(|V(C)|>\ell\). We claim that we can safely ignore (and hence delete) this component when \(\chi\) is successful. Suppose to the contrary that \(V(\sigma)\cap V(C)=Q\
eq\emptyset\). Since \(\chi\) is successful, it must be the case that every vertex in \(N_{G}(Q)\) is coloured blue. However, we know that there exists at least one vertex in \(N_{G}(Q)\) that is coloured red (since \(C\) is a connected component of \(G[V_{\mathcal{R}}]\) and all vertices in \(C\) are coloured red).