# Vertex Cover Reconfiguration and Beyond +
## 5 Polynomial-Time Algorithms
### Cactus Graphs
Next, we show that if \(G[S_{R}\cup T_{A}]\) has no vertex \(v\in S_{R}\) such that \(|N_{G[S_{R}\cup T_{A}]}(v)|\leq 1\) and no cycle \(Y\) such that all vertices in \(Y\cap S_{R}\) have degree exactly two in \(G[S_{R}\cup T_{A}]\), then \(|S_{R}|<|T_{A}|\). We let \(S^{x}\) denote the set of vertices in \(S_{R}\) having degree \(x\) in \(G[S_{R}\cup T_{A}]\). Since \(G[S_{R}\cup T_{A}]\) has no vertex \(v\in S_{R}\) such that \(|N_{G[S_{R}\cup T_{A}]}(v)|\leq 1\), we know that \(S^{2}\) cannot be empty. In addition, since there is no cycle \(Y\) in \(G[S_{R}\cup T_{A}]\) such that all vertices in \(Y\cap S_{R}\) have degree exactly two in \(G[S_{R}\cup T_{A}]\), any cycle involving a vertex in \(S^{2}\) must also include a vertex from \(\bigcup_{i\geq 3}S^{i}\). It follows that \(\bigcup_{i\geq 3}S^{i}\) is a feedback vertex set (a set whose removal destroys all cycles) of \(G[S_{R}\cup T_{A}]\), and \(G[S^{2}\cup T_{A}]\) is a forest. We let \(m_{s}\) denote the maximum degree in \(G[S_{R}\cup T_{A}]\) of any vertex in \(S_{R}\). Since each edge in \(G[S_{R}\cup T_{A}]\) has one endpoint in \(S_{R}\),  
\[\sum_{i=2}^{m_{s}}i|S^{i}|\leq|E(G[S_{R}\cup T_{A}])| \tag{4}\]  
and since each vertex in \(S_{R}\) is in some \(S^{i}\) and using (1), we can rewrite (4) as:  
\[\sum_{i=2}^{m_{s}}i|S^{i}|\leq\left(\sum_{i=2}^{m_{s}}|S^{i}|\right)+|T_{A}|-1 +|\mathcal{C}(G[S_{R}\cup T_{A}])|. \tag{5}\]  
To bound \(|\mathcal{C}(G[S_{R}\cup T_{A}])|\), we note that since no edge can belong to more than one cycle in a cactus graph, any vertex \(v\in S^{x}\) can be involved in at most \(\lfloor\frac{x}{2}\rfloor\) cycles. Combining this observation with the fact that any cycle involving a vertex in \(S^{2}\) must also include a vertex from \(\bigcup_{i\geq 3}S^{i}\), we have:  
\[\sum_{i=2}^{m_{s}}i|S^{i}| \leq\left(\sum_{i=2}^{m_{s}}|S^{i}|\right)+|T_{A}|-1+\left(\sum_{ i=3}^{m_{s}}\lfloor\frac{i}{2}||S^{i}|\right)\] \[\leq|S^{2}|+\left(\sum_{i=3}^{m_{s}}\left(1+\lfloor\frac{i}{2} \rfloor\right)|S^{i}|\right)+|T_{A}|-1 \tag{6}\]  
Finally, by rewriting \(\sum_{i=2}^{m_{s}}i|S^{i}|\) as \(2|S^{2}|+\sum_{i=3}^{m_{s}}i|S^{i}|\) and given that \(i-(1+\lfloor\frac{i}{2}\rfloor)\geq 1\) for \(i\geq 3\), we obtain the desired bound:\[2|S^{2}|+\sum_{i=3}^{m_{s}}i|S^{i}| \leq|S^{2}|+\left(\sum_{i=3}^{m_{s}}{(1+\lfloor\frac{i}{2}\rfloor) |S^{i}|}\right)+|T_{A}|-1\] \[\leq|S_{R}|+|T_{A}|-1+|\mathcal{M}(G[S_{R}\cup T_{A}])| \tag{1}\]0 \[\leq|S_{R}|+|T_{A}|-1+|\mathcal{M}(G[S_{R}\cup T_{A}])| \tag{1}\]1 \[\leq|S_{R}|+|T_{A}|-1+|\mathcal{M}(G[S_{R}\cup T_{A}])| \tag{1}\]2  
This completes the proof. Lemma 5: _If \(G\) is a cactus graph and \(S\) and \(T\) are vertex covers of \(G\), then finding a two-bounded prefix from \(S\) to some vertex cover \(S^{\prime}\) (or from \(T\) to some vertex cover \(T^{\prime}\)) of \(G\) can be accomplished in time polynomial in \(n\)._  
Proof: To find a two-bounded prefix from \(S\) to some vertex cover \(S^{\prime}\) (or from \(T\) to some vertex cover \(T^{\prime}\)), we simply need to satisfy one of the conditions of Lemma 3, which can both be checked in time polynomial in \(n\). Since \(G[S_{R}\cup T_{A}]\) is a cactus graph, we know from Lemma 4 that one of them must be true. Theorem 5.3: _If \(S\) and \(T\) are of size at most \(k-2\), then vertex cover reconfiguration on cactus graphs can be solved in time polynomial in \(n\)._  
Proof: From Lemma 4, we know that for any cactus graph \(G\) and two vertex covers \(S\) and \(T\) of \(G\), then either \(S\xleftarrow{2,T}S^{\prime}\) or \(T\xleftarrow{2,S}T^{\prime}\), where \(S^{\prime}\) and \(T^{\prime}\) are some vertex covers of \(G\). In addition, Lemma 5 shows that such two-bounded prefixes can be found in time polynomial in \(n\). By combining these facts, we can now apply Lemma 2. That is, if \(|S|\leq k-2\) and \(|T|\leq k-2\), a reconfiguration sequence of length \(|S_{R}|+|T_{A}|\) from \(S\) to \(T\) can be found in time polynomial in \(n\).