# Vertex Cover Reconfiguration and Beyond +
## 4 Hardness Results
To form \(W\), we choose \(\{x_{i}\mid v_{i}\in V(K)\}\cup\{z_{i}\mid e_{i}\in E(K)\}\), that is the vertices in \(X\) corresponding to the vertices in the clique and the vertices in \(Z\) corresponding to the edges in the clique. Clearly, \(H\) is a subset of size \(k\) of \(B\), and \(W\) is a subset of size \(k+\binom{k}{2}\) of \(A\); this implies that \(|W|-|H|\geq d=\binom{k}{2}\), as required. To see why \(N_{G^{\prime}}(W)=H\), it suffices to note that every vertex \(x_{i}\in W\) is connected to exactly one vertex \(y_{i}\in H\), and every degree-two vertex \(z_{i}\in W\) corresponds to an edge in \(K\) whose endpoints \(v_{i}v_{j}\) must have corresponding vertices in \(H\). Moreover, due to \(E_{1}\), there is a matching between the vertices of \(H\) and the vertices of \(W\) in \(X\) and, hence, a matching in \(G^{\prime}[W\cup H]\) that saturates \(H\). We now assume that \(G^{\prime}\) has a \((k,\binom{k}{2})\)-constrained crown \((W,H)\) such that \(W\subseteq X\cup Z\) and \(H\subseteq Y\). It suffices to show that \(|H|\) must be equal to \(k\), \(|W\cap Z|\) must be equal to \(\binom{k}{2}\) and, hence, \(|W\cap X|\) must be equal to \(k\); from this, we can conclude that the vertices in \(\{v_{i}\mid y_{i}\in H\}\) form a clique of size \(k\) in \(G\) as \(|W\cap Z|=\binom{k}{2}\), requiring that edges exist between each pair of vertices in the set \(\{v_{i}\mid y_{i}\in H\}\). Moreover, since \(|W\cap X|=k\) and \(N_{G^{\prime}}(W)=H\), a matching that saturates \(H\) can be easily found by simply picking all edges \(x_{i}y_{i}\) for \(y_{i}\in H\). To prove the sizes of \(H\) and \(W\), we first observe that since \(|H|\leq k\), \(N_{G^{\prime}}(W)=H\), and each vertex in \(Y\) has exactly one neighbour in \(X\), we know that \(|W\cap X|\leq|H|\leq k\). Moreover, since \(|W|=|W\cap X|+|W\cap Z|\) and \(|W|-|H|\geq\binom{k}{2}\), we know that \(|W\cap Z|=|W|-|W\cap X|\geq\binom{k}{2}+|H|-|W\cap X|\geq\binom{k}{2}\). If \(|W\cap Z|=\binom{k}{2}\), our proof is complete, since by our construction of \(G^{\prime}\), \(H\) is a set of at most \(k\) vertices in the original graph \(G\), and the subgraph induced by those vertices in \(G\) has \(\binom{k}{2}\) edges. Hence, \(|H|\) must be equal to \(k\). Suppose instead that \(|W\cap Z|>\binom{k}{2}\). In this case, since each vertex of \(Z\) has degree two, the number of neighbours of \(W\cap Z\) in \(Y\) is greater than \(k\), violating the assumptions that \(N_{G^{\prime}}(W)=H\) and \(|H|\leq k\). We can now show the main result of this section:  
Theorem 3.1: _VCR parameterized by \(\ell\) and restricted to bipartite graphs is W[1]-hard._  
Proof. : We give a reduction from the \((t,d)\)-bipartite constrained crown to vertex cover reconfiguration in bipartite graphs. For \((G=(A\cup B,E),t,d)\), an instance of the \((t,d)\)-bipartite constrained crown, \(A=\{a_{1},\ldots,a_{|A|}\}\) and \(B=\{b_{1},\ldots,b_{|B|}\}\), we form \(G^{\prime}=(X\cup Y\cup U\cup V,E_{1}\cup E_{2})\) such that \(X\) and \(Y\) correspond to the vertex sets \(A\) and \(B\), \(E_{1}\) connects vertices in \(X\) and \(Y\) corresponding to vertices in \(A\) and \(B\) joined by edges in \(G\) and \(U\), \(V\) and \(E_{2}\) form a complete bipartite graph \(K_{d+t,d+t}\). More formally, \(X=\{x_{1},\ldots,x_{|A|}\}\), \(Y=\{y_{1},\ldots,y_{|B|}\}\), \(U=\{u_{1},\ldots,u_{d+t}\}\), \(V=\{v_{1},\ldots,v_{d+t}\}\), \(E_{1}=\{x_{i}y_{j}\mid a_{i}y_{j}\in E(G)\}\) and \(E_{2}=\{u_{i}v_{j}\mid 1\leq i\leq d+t,1\leq j\leq d+t\}\). We let \((G^{\prime},S,T,k=|A|+d+2t,\ell=4d+6t)\) be an instance of VCR, where \(S=X\cup U\) and \(T=X\cup V\). Clearly, \(|S|=|T|=|A|+d+t\). We claim that \(G\) has a \((k,d)\)-constrained crown \((W,H)\) such that \(W\subseteq A\) and \(H\subseteq B\) if and only if there is a path of length at most \(4d+6t\) from \(S\) to \(T\). If \(G\) has such a pair \((W,H)\), we form a reconfiguration sequence of length at most \(4d+6t\) as follows:  
1. Add each vertex \(y_{i}\) such that \(b_{i}\in H\). The resulting vertex cover size is \(|A|+d+t+|H|\). 2.