# Vertex Cover Reconfiguration and Beyond +
## 4 Hardness Results  
In earlier work establishing the \(\mathsf{W[1]}\)-hardness of the VCR problem parameterized by \(\ell\) on general graphs, it was also shown that the problem becomes fixed-parameter tractable whenever \(\ell=|S_{R}\cup T_{A}|\)[10] (as we know exactly which vertices have to be touched, it is only a question of finding the right order of additions and removals). When \(|S_{R}\cup T_{A}|=n\), we know from Proposition 2 that \(\ell\geq n\), since every vertex in \(S_{R}\cup T_{A}\) must be touched at least once. Moreover, Proposition 1 implies that whenever \(|S_{R}\cup T_{A}|=n\), the input graph must be bipartite. It is thus natural to ask about the complexity of the problem when \(\ell<n\) and the input graph is restricted to be bipartite. Since the vertex cover problem is known to be solvable in time polynomial in \(n\) on bipartite graphs, our result is, to the best of our knowledge, the first example of a problem solvable in polynomial time whose reconfiguration version is \(\mathsf{W[1]}\)-hard. For a graph \(G\), a crown is a pair \((W,H)\) satisfying the following properties: (i) \(W\
eq\emptyset\) is an independent set of \(G\); (ii) \(N_{G}(W)=H\); and (iii) there exists a matching in \(G[W\cup H]\) that saturates \(H\)[16; 17]. \(H\) is called the head of the crown, and the width of the crown is \(|H|\). Crown structures have played a central role in the development of efficient kernelization algorithms for the vertex cover problem [16; 17]. We define the closely-related notion of \((t,d)\)-constrained crowns and show in the remainder of this section that the complexity of finding such structures in a bipartite graph is central for determining the complexity of the reconfiguration problem. \((t,d)\)-bipartite constrained crown  
**Input**: A bipartite graph \(G=(A\cup B,E)\) and two positive integers \(t\) and \(d\)  
**Parameters**: \(t\) and \(d\)  
**Question**: Does \(G\) have a \((t,d)\)-constrained crown \((W,H)\) such that \(W\subseteq A\) and \(H\subseteq B\)? **Lemma 1**: _The \((t,d)\)-bipartite constrained crown is \(\mathsf{W[1]}\)-hard even when the input graph, \(G=(A\cup B,E)\), is \(C_{4}\)-free and all vertices in \(A\) have degree at most two._  
Proof. : We give a reduction from the \(k\)-clique, known to be \(\mathsf{W[1]}\)-hard, to the \((k,{k\choose 2})\)-bipartite constrained crown. For \((G,k)\) an instance of \(k\)-clique, we let \(V(G)=\{v_{1},\ldots,v_{n}\}\) and \(E(G)=\{e_{1},\ldots,e_{m}\}\). We first form a bipartite graph \(G^{\prime}=((X\cup Z)\cup Y,E_{1}\cup E_{2})\), where vertex sets \(X\) and \(Y\) contain one vertex for each vertex in \(V(G)\) and \(Z\) contains one vertex for each edge in \(E(G)\). More formally, we set \(X=\{x_{1},\ldots,x_{n}\}\), \(Y=\{y_{1},\ldots,y_{n}\}\), and \(Z=\{z_{1},\ldots,z_{m}\}\). The edges in \(E_{1}\) join each pair of vertices \(x_{i}\) and \(y_{i}\) for \(1\leq i\leq n\) and the edges in \(E_{2}\) join each vertex \(z\) in \(Z\) to the two vertices \(y_{i}\) and \(y_{j}\) corresponding to the endpoints of the edge in \(E(G)\) to which \(z\) corresponds. Since each edge either joins vertices in \(X\) and \(Y\) or vertices in \(Y\) and \(Z\), it is not difficult to see that the vertex sets \(X\cup Z\) and \(Y\) form a bipartition. By our construction, \(G^{\prime}\) is \(C_{4}\)-free; vertices in \(X\) have degree one, and since there are no double edges in \(G\), i.e., two edges between the same pair of vertices, no pair of vertices in \(Y\) can have more than one common neighbour in \(Z\). For \((G^{\prime},k,\binom{k}{2})\) an instance of \((k,\binom{k}{2})\)-BCC, \(A=X\cup Z\) and \(B=Y\), we claim that \(G\) has a clique of size \(k\) if and only if \(G^{\prime}\) has a \((k,\binom{k}{2})\)-constrained crown \((W,H)\) such that \(W\subseteq A\) and \(H\subseteq B\). If \(G\) has a clique \(K\) of size \(k\), we set \(H=\{y_{i}\mid v_{i}\in V(K)\}\), namely the vertices in \(Y\) corresponding to the vertices in the clique.