# Vertex Cover Reconfiguration and Beyond +
## 6 FPT Algorithms
### NP-Hardness on Four-Regular Graphs
Finally, whenever a sequin pair \(p\in S^{\prime}_{s}\) has two neighbours in \(I\), then \(t_{b},t_{s}\geq 1\), as at least one bead neighbouring the sequin pair joined with \(p\) must be in \(S^{\prime}_{b}\). Every other sequin pair \(p^{\prime}\in S^{\prime}_{s}\), \(p^{\prime}\
eq p\), with two neighbours in \(I\) will force at least one additional connected component in either \(Z[S^{\prime}_{b}\cup N_{Z}(S^{\prime}_{b})]\) or \(Z[S^{\prime}_{s}\cup N_{Z}(S^{\prime}_{s})]\) since \(W_{k}\) contains a single joining biclique between any two necklaces. Therefore, the total number of connected components is \(t_{b}+t_{s}\geq\frac{|I|}{2}\). Putting it all together, we get:  
\[\frac{40}{50}|S^{\prime}_{b}|+\frac{15}{50}|S^{\prime}_{s}|+2(t_{ b}-1)+t_{s} \geq\frac{2}{10}|I|+\frac{3}{10}|I|+\frac{5}{10}|I|+t_{b}-2\] \[\geq|I|-2 \tag{9}\]  
Combining Equations (8) and (9), we get:  
\[|N_{Z}(S^{\prime})|+2 \geq\frac{6}{5}|S^{\prime}|+\frac{40}{50}|S^{\prime}_{b}|+\frac{1 5}{50}|S^{\prime}_{s}|+2(t_{b}-1)+t_{s}-(|I|-2)\] \[\geq\frac{6}{5}|S^{\prime}| \tag{10}\]  
Therefore, \(V(S,\alpha[1,x])\) is a vertex cover of \(W_{k}\) of size at least \(3k^{2}+k-2\), as needed. To show the \(f(k)\leq k+3\) upper bound, we show that \((W_{k},S,T,3k^{2}+k+3,6k^{2})\) is a yes-instance by providing an actual reconfiguration sequence:  
1. Add all \(k\) beads in \(L_{1}\). Since \(S\) is a vertex cover of \(W_{k}\), we know that the additional \(k\) beads will result in a vertex cover of size \(3k^{2}+k\). 2. Add both vertices in \(p^{u}_{1,1}\), and remove both vertices in \(p^{l}_{1,1}\). The removal of both vertices in \(p^{l}_{1,1}\) is possible since we added all their neighbours in \(L_{1}\) (Step (1)) and \(U_{1}\). The size of a vertex cover reaches \(3k^{2}+k+2\) after the additions and then drops back to \(3k^{2}+k\). 3. Repeat Step (2) for all sequin pairs \(p^{u}_{i,1}\) and \(p^{l}_{1,i}\) for \(2\leq i\leq k\). The size of a vertex cover is again \(3k^{2}+k\) once Step (3) is completed. Step (2) is repeated a total of \(k\) times. After every repetition, we have a vertex cover of \(W_{k}\) since all beads in \(L_{1}\) were added in Step (1), and the remaining neighbours of each sequin pair in \(U_{i}\) are added prior to the removals. 4. Add both vertices in \(p^{u}_{1,2}\), and remove vertex \(p^{u}_{1,2}\). 5. Add \(b^{l}_{2,1}\) and \(b^{l}_{2,2}\). At this point, the size of a vertex cover is \(3k^{2}+k+3\). 6. Remove both vertices in \(p^{l}_{2,1}\). 7. Repeat Steps (4), (5) and (6) until all beads in \(L_{2}\) have been added and the sequin pairs removed. When we reach the last sequin pair in \(L_{2}\), \(b^{l}_{2,1}\) was already added, and hence, we gain a surplus of one, which brings the vertex cover size back to \(3k^{2}+k\). 8. Repeat Steps (4) to (7) for every remaining necklace in \(L\). Since every vertex in \(W_{k}\) is touched exactly once, we know that \(\ell=6k^{2}\). In the course of the described reconfiguration sequence, the maximum size of any vertex cover is \(3k^{2}+k+3\). Hence, \(f(k)\leq k+3\). This completes the proof. It would be interesting to close the gap on \(f(k)\), but the existence of such a value is enough to prove the main theorem of this section. Theorem 4.5: _Vertex cover reconfiguration is NP-hard on four-regular graphs._  
Proof. : We prove the result by a reduction from vertex cover compression to vertex cover reconfiguration where the input graph is restricted to be four-regular in both cases. For \((G,C,k)\)an instance of vertex cover compression, we form \(G^{\prime}=(V(G)\cup V(W_{k}),E(G)\cup E(W_{k}))\). We let \((G^{\prime},S,T,3k^{2}+k+f(k)-1,6k^{2}+4k-2)\) be an instance of vertex cover reconfiguration, where \(S=\{e_{i,j}^{\mu}\mid 1\leq i,j\leq k\}\cup\{p_{i,j}^{l}\mid 1\leq i,j\leq k\}\cup C\) and \(T=\{e_{i,j}^{l}\mid 1\leq i,j\leq k\}\cup\{p_{i,j}^{l}\mid 1\leq i,j\leq k\}\cup C\), and \(f(k)\) is the value whose existence was shown in Lemma 6. Clearly, \(|S|=|T|=3k^{2}+k\) and both \(S\) and \(T\) are vertex covers of \(G^{\prime}\).