# Vertex Cover Reconfiguration and Beyond +
## 6 FPT Algorithms
### NP-Hardness on Four-Regular Graphs  
We are now ready to show that vertex cover reconfiguration remains NP-hard even if the input graph is restricted to be four-regular. We use the same ideas as we did in the previous section. Since vertex cover remains NP-hard on four-regular graphs [22] and any algorithm that solves the vertex cover compression problem can be used to solve the vertex cover problem, we get the desired result. The main difference here is that we need to construct a gadget, \(W_{k}\), that is also four-regular. We describe \(W_{k}\) in terms of several component subgraphs, each playing a role in forcing the reconfiguration of vertex covers. A \(k\)-necklace, \(k\geq 4\), is a graph obtained by replacing every edge in a cycle on \(k\) vertices by two vertices and four edges. For convenience, we refer to every vertex on the original cycle as a bead and every new vertex in the resulting graph as a sequin. The resulting graph has \(k\) beads each of degree four and \(2k\) sequins each of degree two. Every two sequins that share the same neighbourhood in a \(k\)-necklace are called a sequin pair. We say two beads are adjacent whenever they share exactly two common neighbours. Similarly, we say two sequin pairs are adjacent whenever they share exactly one common neighbour. Every two adjacent beads (sequin pairs) are linked by a sequin pair (bead). The graph \(W_{k}\) consists of \(2k\) copies of a \(k\)-necklace. We let \(U=\{U_{1},\ldots U_{k}\}\) and \(L=\{L_{1},\ldots L_{k}\}\) denote the first and second \(k\) copies, respectively; for convenience, we use the terms \"upper\" and \"lower\" to mean \"in \(U^{\prime}\) and \"in \(L^{\prime}\)\", respectively. We let \(b^{u}_{i,j}\) and \(b^{l}_{i,j}\) denote the \(j\)-th beads of necklace \(U_{i}\) and \(L_{i}\), respectively, where \(1\leq i\leq k\) and \(1\leq j\leq k\). Beads on each necklace in \(W_{k}\) are numbered consecutively in \"clockwise order\" from one to \(k\). For every two adjacent beads \(b^{x}_{i,j}\) and \(b^{x}_{i,j+1}\), where \(x\in\{u,l\}\), we let \(p^{x}_{i,j}\) denote the sequin pair that links both beads. For each sequin pair \(p^{l}_{i,j}\), we add four edges to form a \(K_{2,2}\) (a joining biclique) with the pair \(p^{u}_{j,i}\), for all \(1\leq i,j\leq k\) (Figure 1); we say that sequin pairs \(p^{l}_{i,j}\) and \(p^{u}_{j,i}\) are joined. All \(k^{2}\) joining bicliques in \(W_{k}\) are vertex disjoint. The total number of vertices in \(W_{k}\) is \(6k^{2}\). Every vertex has degree exactly four; every bead is connected to four sequins from the same necklace, and every sequin is connected to two beads from the same necklace and two other sequins from a different necklace. We let \(S\) be the set containing all upper beads and lower sequins, whereas \(T\) contains all lower beads and upper sequins. Formally, \(S=\{b^{u}_{i,j}\mid 1\leq i,j\leq k\}\cup\{v\in p^{l}_{i,j}\mid 1\leq i,j\leq k\}\) and \(T=\{b^{l}_{i,j}\mid 1\leq i,j\leq k\}\cup\{v\in p^{u}_{i,j}\mid 1\leq i,j\leq k\}\). Each set contains \(3k^{2}\) vertices, that is half the vertices in \(W_{k}\). **Proposition 8**. : \(S\) _and \(T\) are minimum vertex covers of \(W_{k}\)._  
Proof. : We need at least \(2k^{2}\) vertices to cover the edges in the \(k^{2}\) vertex disjoint joining bicliques contained in \(W_{k}\). Moreover, any minimal vertex cover \(C\) of \(W_{k}\) that includes a vertex \(v\) from a sequin pair \(p^{x}_{i,j}=\{v,w\}\), where \(x\in\{u,l\}\), must also include \(w\). Otherwise, the two beads linking \(p^{x}_{i,j}\) to its adjacent sequin pairs must be in \(C\) to cover the edges incident on \(w\), making \(v\) removable. Hence, any minimal vertex cover \(C\) of \(W_{k}\) must include either one or both sequin pairs in a joining biclique. We let \(x\) denote the number of joining bicliques from which two sequin pairs are included in \(C\). Similarly, we let \(y\) denote the number of joining bicliques from which only one sequin pair is included in \(C\). Hence, \(x+y=k^{2}\) and \(|C|\geq 4x+2y\).