# Vertex Cover Reconfiguration and Beyond +
## 6 FPT Algorithms
### NP-Hardness on Four-Regular Graphs
When \(y=0\), \(|C|\geq 4k^{2}\) and \(C\) cannot be a minimum vertex cover, as \(S\) and \(T\) are both vertex covers of \(W_{k}\) of size \(3k^{2}\). When \(y\geq 1\), we are left with at least \(y\) uncovered edges incident to the sequin pairs not in \(C\). Those edges must be covered using at least \(y\) beads and, hence, \(|C|\geq 4x+3y\). If we assume \(4x+3y<3k^{2}\), we get a contradiction since \(4x+4y=4k^{2}<3k^{2}+y\) and \(k^{2}<y\). Therefore, \(S\) and \(T\) must be minimum vertex covers of \(W_{k}\). To prove the next two results, we consider the representation of reconfiguration sequences as edit sequences. Since \(S\) is a minimal vertex cover of \(W_{k}\), \(\alpha\) cannot start with a vertex removal. Since \(V(S,\alpha[1,|\alpha|-1])\) is a vertex cover of \(W_{k}\), \(|S|=|T|\) and \(S\) and \(T\) are minimum vertex covers of \(W_{k}\), \(\alpha\) cannot end with a vertex addition. Moreover, if \(|\alpha|=6k^{2}\), then \(\alpha\) must touch every vertex in \(W_{k}\) exactly once. **Proposition 9**. : _Any (valid) edit sequence \(\alpha^{\prime}\) of length \(6k^{2}\) from \(S\) to \(T\) can be converted into a (valid) edit sequence \(\alpha\) from \(S\) to \(T\) such that \(|\alpha|=|\alpha^{\prime}|=6k^{2}\), \(|V(S,\alpha[1,p])|\leq|V(S,\alpha^{\prime}[1,p])|\), for all \(1\leq p\leq|\alpha|\), and any two vertices \(u\) and \(v\) from the same sequin pair in \(W_{k}\) are either added in the same maximal addition segment or removed in the same maximal removal segment of \(\alpha\). Consequently, \(\textsf{cap}(\alpha)\leq\textsf{cap}(\alpha^{\prime})\)._  
Proof. : Both vertices in a sequin pair share the same neighbourhood. Hence, when \(u\) is removed, all of its neighbours must have been added, making \(v\) also removable. Moreover, since every vertex is  
Figure 1: The graph \(W_{4}\) (the edges of only one of the \(k^{2}\) joining bicliques is shown). touched exactly once in \(\alpha^{\prime}\), none of the neighbours of \(u\) and \(v\) will be touched in \(\alpha^{\prime}\) after the removal of \(u\). Therefore, if \(v\) is not removed in the same maximal removal segment as \(u\), then we obtain \(\alpha\) by shifting the removal of \(v\), so that it happens immediately after the removal of \(u\). It is not hard to see that \(|\alpha|=|\alpha^{\prime}|=6k^{2}\) and \(|V(S,\alpha[1,p])|\leq|V(S,\alpha^{\prime}[1,p])|\), for all \(1\leq p\leq|\alpha|\). For the case of additions, if only \(u\) is added in some maximal addition segment \(\beta\), then none of its neighbours can yet be removed. Let \(\gamma\) be the maximal addition segment in which \(v\) is added (which occurs after \(\beta\) in \(\alpha^{\prime}\)). We obtain \(\alpha\) by shifting the addition of \(u\) from \(\beta\) to \(\gamma\). Lemma 6: _There exists a function of \(k\), \(f(k)\), such that \((W_{k},S,T,3k^{2}+f(k),\ell)\) is a yes-instance and \((W_{k},S,T,3k^{2}+f(k)-1,\ell)\) is a no-instance of vertex cover reconfiguration for \(\ell=6k^{2}\). Moreover, \(k-2\leq f(k)\leq k+3\)._  
Proof. : To show that such an \(f(k)\) exists, we first prove the \(k-2\) lower bound by showing that any valid edit sequence \(\alpha\) of length \(6k^{2}\) from \(S\) to \(T\) must have some prefix where the number of vertex additions \(\#a\) minus the number of vertex removals \(\#r\) is at least \(k-2\), i.e., \(\#a-\#r\geq k-2\). In fact, we will show that the aforementioned property holds for any valid edit sequence \(\alpha\) of length \(6k^{2}\) in which two vertices from the same sequin pair are always added or removed in the same maximal addition or removal segment, respectively. Considering only such sequences is sufficient because, from Proposition 9, we know that any sequence \(\alpha^{\prime}\) of length \(6k^{2}\) can be transformed into such a sequence \(\alpha\) so that \(|V(S,\alpha[1,p])|\leq|V(S,\alpha^{\prime}[1,p])|\), for all \(1\leq p\leq|\alpha|\).