# Vertex Cover Reconfiguration and Beyond +
## 6 FPT Algorithms
### NP-Hardness on Four-Regular Graphs
In other words, if \(\alpha^{\prime}\) has no prefix with \(\#a-\#r\geq k-2\) (but \(\alpha\) does), then \(\texttt{cap}(\alpha^{\prime})<\texttt{cap}(\alpha)\), a contradiction. We let position \(x\), \(1\leq x\leq|\alpha|\), be the smallest position such that \(\alpha[1,x]\) contains exactly \(5k\) vertex removals. Those \(5k\) vertices correspond to a set \(S^{\prime}\subset S\), as \(\alpha\) touches every vertex exactly once. The claim is that \(\alpha[1,x]\) must contain at least \(6k-2\) vertex additions. We let \(T^{\prime}\subset T\) denote the set of added vertices in \(\alpha[1,x]\). Since \(N_{W_{k}}(S^{\prime})\subseteq T^{\prime}\), we complete the proof of the lower bound by showing that \(|T^{\prime}|\geq|N_{W_{k}}(S^{\prime})|\geq\frac{6}{8}|S^{\prime}|-2\geq 6k-2\). To do so, we show that for any \(S^{\prime}\subset S\) of size \(5k\), \(N_{W_{k}}(S^{\prime})\subseteq T^{\prime}\) contains at least \(\frac{6}{8}|S^{\prime}|-2=6k-2\) vertices. In what follows, we restrict our attention to the bipartite graph \(Z=W_{k}[S^{\prime}\cup T^{\prime}]\), and we let \(S^{\prime}\) and \(T^{\prime}\) denote the two partitions of \(Z\). We subdivide \(S^{\prime}\) into two sets: \(S^{\prime}_{b}\) contains upper beads, and \(S^{\prime}_{s}\) contains lower sequins. Since every vertex in \(S^{\prime}_{b}\) has four neighbours in \(T^{\prime}\) and adjacent beads share exactly two neighbours, we have \(|N_{Z}(S^{\prime}_{b})|\geq 2|S^{\prime}_{b}|\), and equality occurs whenever \(S^{\prime}_{b}\) contains \(2k\) beads from the same two upper necklaces. Whenever \(S^{\prime}_{b}\) contains fewer than \(2k\) beads and \(Z[S^{\prime}_{b}\cup N_{Z}(S^{\prime}_{b})]\) consists of \(t_{b}\geq 1\) connected components, at least one bead from each component (except possibly the first) will be adjacent to at most one other bead in the same component. Therefore, \(|N_{Z}(S^{\prime}_{b})|\geq 2|S^{\prime}_{b}|+2(t_{b}-1)\). Proposition 9 implies that \(T^{\prime}\) will always contain both vertices of any sequin pair. Since we are only considering vertices in \(V(\alpha[1,x])\), some sequins in \(S^{\prime}_{s}\) might be missing the other sequin in the corresponding pair. However, all the neighbours of the sequin pair have to be in \(T^{\prime}\), so we assume without loss of generality that vertices in \(S^{\prime}_{s}\) can be grouped into sequin pairs. Every sequin pair in \(S^{\prime}_{s}\) has four neighbours in \(T^{\prime}\). Adjacent sequin pairs share exactly one neighbour. Hence, \(|N_{Z}(S^{\prime}_{s})|\geq\frac{3}{2}|S^{\prime}_{s}|\), and equality occurs whenever \(S^{\prime}_{s}\) contains \(k\) sequin pairs of a single lower necklace. Whenever \(S^{\prime}_{s}\) contains fewer than \(k\) sequin pairs and \(Z[S^{\prime}_{s}\cup N_{Z}(S^{\prime}_{s})]\) consists of \(t_{s}\geq 1\) connected components, at least one sequin pair from each component will be adjacent to at most one other sequin pair in the same component. Therefore, \(|N_{Z}(S^{\prime}_{s})|\geq\frac{3}{2}|S^{\prime}_{s}|+t_{s}\). Combining the previous observations, we know that when either \(S^{\prime}_{b}\) or \(S^{\prime}_{s}\) is empty, \(|N_{Z}(S^{\prime})|\geq\frac{6}{8}|S^{\prime}|\), as needed. When both are not empty, we let \(I=N_{Z}(S^{\prime}_{b})\cap N_{Z}(S^{\prime}_{s})\). Hence, \(|N_{Z}(S^{\prime}_{b})|+|N_{Z}(S^{\prime}_{s})|-|I|\geq 2|S^{\prime}_{b}|+2(t_{b}-1)+ \frac{3}{2}|S^{\prime}_{s}|+t_{s}-|I|\), and we rewrite it as:  
\[|N_{Z}(S^{\prime})|+2\geq\frac{100}{50}|S^{\prime}_{b}|+\frac{75}{50}|S^{ \prime}_{s}|+2(t_{b}-1)+t_{s}-(|I|-2) \tag{8}\]We now bound the size of \(I\). Note that \(I\) can only contain upper sequin pairs joined with sequin pairs in \(S^{\prime}_{s}\). As every sequin pair in \(S^{\prime}_{s}\) has either zero or two neighbours in \(I\), \(|S^{\prime}_{s}|\geq|I|\). Moreover, for every two sequin pairs in \(S^{\prime}_{s}\) having two neighbours in \(I\), there must exist at least one vertex in \(S^{\prime}_{b}\), which implies \(|S^{\prime}_{b}|\geq\frac{|I|}{4}\).