# Vertex Cover Reconfiguration and Beyond +
## 5 Polynomial-Time Algorithms
### Cactus Graphs
The reconfiguration sequence from \(S\) to \(S^{\prime}\) is a one-bounded prefix and can be found in time polynomial in \(n\). For the second case, we let \(Y\) be a cycle in \(G[S_{R}\cup T_{A}]\), and we partition the vertices of the cycle into two sets; \(Y_{S}=Y\cap S_{R}\) and \(Y_{T}=Y\cap T_{A}\). Since \(G[S_{R}\cup T_{A}]\) is bipartite, we know that \(|Y_{S}|=|Y_{T}|\). Since all vertices in \(Y_{S}\) have degree exactly two in \(G[S_{R}\cup T_{A}]\), it follows that \(N_{G[S_{R}\cup T_{A}]}(Y_{S})\subseteq Y_{T}\). Therefore, a reconfiguration sequence from \(S\) to some vertex cover \(S^{\prime}\) that adds all vertices in \(Y_{T}\) (one by one) and then removes all vertices in \(Y_{S}\) (one by one) will satisfy Conditions (1), (3) and (4) from Definition 1 for any value of \(c\). For \(c=2\), such a sequence will not satisfy Condition (2) if the cycle has at least six vertices (i.e., \(|Y_{T}|\geq 3\)). However, using the fact that every vertex in \(Y_{S}\) has degree exactly two in \(G[S_{R}\cup T_{A}]\), we can find a reconfiguration sequence from \(S\) to \(S^{\prime}\) in which no vertex cover has a size greater than \(|S|+2\). To do so, we restrict our attention to \(G[Y_{S}\cup Y_{T}]\). Since \(Y\) is an even cycle, we can label all the vertices of \(Y\) in clockwise order from zero to \(|Y|-1\) such that all vertices in \(Y_{S}\) receive even labels. The reconfiguration sequence from \(S\) to \(S^{\prime}\) starts by adding the two vertices labelled \(1\) and \(|Y|-1\). After doing so, the vertex labelled \(0\) is removed. Next, to remove the vertex labelled \(2\), we only need to add the vertex labelled \(3\). The same process is repeated for all vertices with even labels up to \(|Y|-4\). Finally, when we reach the vertex labelled \(|Y|-2\), both of its neighbours will have already been added, and we can simply remove it. Hence, we have a two-bounded prefix from \(S\) to \(S^{\prime}\), and it is not hard to see that finding this reconfiguration sequence can be accomplished in time polynomial in \(n\). When the appropriate assumptions hold, we can show the symmetric case \(T\xleftrightarrow{2,S}\). \(T^{\prime}\) using similar arguments. Lemma 4: _If \(G\) is a cactus graph and \(S\) and \(T\) are two vertex covers of \(G\), then there exists a vertex cover \(S^{\prime}\) (or \(T^{\prime}\)) of \(G\) such that \(S\xleftrightarrow{2,T}S^{\prime}\) (or \(T\xleftrightarrow{2,S}T^{\prime}\))._  
Proof. : We assume that \(|S_{R}|\geq|T_{A}|\), as we can swap the roles of \(S\) and \(T\) whenever \(|S_{R}|<|T_{A}|\). We observe that every connected component of \(G[S_{R}\cup T_{A}]\) is a cactus graph since every induced subgraph of a cactus graph is also a cactus graph. Since we assume \(|S_{R}|\geq|T_{A}|\), at least one connected component \(X\) of \(G[S_{R}\cup T_{A}]\) must satisfy \(|V(X)\cap S_{R}|\geq|V(X)\cap T_{A}|\). To prove the lemma, we show that if neither condition of Lemma 3 applies to \(X\), it must be the case that \(|V(X)\cap S_{R}|<|V(X)\cap T  
Since \(G[S_{R}\cup T_{A}]\) is a cactus graph, we can apply Propositions 5 and 6 to get:  
\[|E(G[S_{R}\cup T_{A}])| =|S_{R}|+|T_{A}|-1+|\mathcal{C}(G[S_{R}\cup T_{A}])|\] \[\leq|S_{R}|+|T_{A}|-1+|\mathcal{M}(G[S_{R}\cup T_{A}])| \tag{1}\]  
Moreover, since \(G[S_{R}\cup T_{A}]\) is bipartite (Proposition 1), the size of a maximum matching in \(G[S_{R}\cup T_{A}]\) is less than or equal to \(min(|S_{R}|,|T_{A}|)\). Therefore:  
\[|\mathcal{C}(G[S_{R}\cup T_{A}])|\leq|\mathcal{M}(G[S_{R}\cup T_{A}])|\leq|S_{ R}| \tag{2}\]  
Combining (1) and (2), we get:  
\[|E(G[S_{R}\cup T_{A}])| =|S_{R}|+|T_{A}|-1+\mathcal{C}(G[S_{R}\cup T_{A}])\] \[\leq 2|S_{R}|+|T_{A}|-1 \tag{3}\]  
If the minimum degree in \(G[S_{R}\cup T_{A}]\) of any vertex in \(S_{R}\) is three or more, then \(3|S_{R}|\leq|E(G[S_{R}\cup T_{A}])|\leq 2|S_{R}|+|T_{A}|-1\) and thus \(|S_{R}|\leq|T_{A}|-1\), contradicting our assumption that \(|S_{R}|\geq|T_{A}|\). Hence, \(G[S_{R}\cup T_{A}]\) must have at least one vertex of degree two in \(S_{R}\).