# Vertex Cover Reconfiguration and Beyond +
## 5 Polynomial-Time Algorithms
### Cactus Graphs  
A cactus graph \(G\)[19] is a connected graph in which every edge belongs to at most one cycle. We let \(\mathcal{C}(G)\) denote the set of all cycles in \(G\). We say vertex \(v\in V(G)\) is a join vertex if \(v\) belongs to a cycle and \(N_{G}(v)\geq 3\). The following proposition is a consequence of the fact that a maximal matching \(\mathcal{M}(G)\) of a cactus graph \(G\) can contain an edge from each cycle in \(\mathcal{C}(G)\). **Proposition 5**: _For a cactus graph \(G\), the number of cycles in \(G\) is bounded above by the size of a maximum matching \(\mathcal{M}(G)\), i.e., \(|\mathcal{C}(G)|\leq|\mathcal{M}(G)|\)._  
The next proposition is a consequence of the fact that for any cactus graph \(G\), we can obtain a spanning tree of \(G\) by removing a single edge from every cycle in \(G\). **Proposition 6**: _For a cactus graph \(G\) and \(T_{G}\) a spanning tree of \(G\), the total number of edges in \(G\) is equal to the number of edges in \(T_{G}\) plus the total number of cycles in \(G\), i.e., \(|E(G)|=|E(T_{G})|+|\mathcal{C}(G)|=|V(T_{G})|-1+|\mathcal{C}(G)|\)._  
Any graph with no even cycles (as subgraphs) is a cactus graph [20]. For a graph \(G\) with no even cycles and any two vertex covers, \(S\) and \(T\), of \(G\), we know that \(G[S_{R}\cup T_{A}]\) must be a forest, i.e., a bipartite graph with no even cycles (Proposition 1). Proposition 7 follows from the fact that in the proof of Theorem 2, the fact that \(G\) is a tree is used only to determine that \(G[S_{R}\cup T_{A}]\) must be a forest. Therefore, using the same proof as in Theorem 2, we can show:  
**Proposition 7**: _Vertex cover reconfiguration on graphs with no even cycles can be solved in time polynomial in \(n\)._  
In the remainder of this section, we generalize Proposition 7 to all cactus graphs assuming that the given vertex covers \(S\) and \(T\) are of size at most \(k-2\). To do so, we first show, in Lemmas 3 and 4, that the third condition of Lemma 2 is satisfied for cactus graphs with \(c=2\). In Lemma 5, we show how two-bounded prefixes can be found in time polynomial in \(n\), which leads to Theorem 3. We note that a similar result was proven independently by [PERSON] et al. [21] via completely different methods. **Lemma 3**: _Given two vertex covers \(S\) and \(T\) of \(G\), 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}\)) if one of the following conditions holds:_  
1. \(G[S_{R}\cup T_{A}]\) _has a vertex_ \(v\in S_{R}\) _(_\(v\in T_{A}\)_) such that_ \(|N_{G[S_{R}\cup T_{A}]}(v)|\leq 1\)_; or__;_
2. _there exists a cycle_ \(Y\) _in_ \(G[S_{R}\cup T_{A}]\) _such that all vertices in_ \(Y\cap S_{R}\) _(_\(Y\cap T_{A}\)_) have degree exactly two in_ \(G[S_{R}\cup T_{A}]\)_._  
_Moreover, both conditions can be checked in time polynomial in \(n\), and when one of them is true, the corresponding two-bounded prefix can be found in time polynomial in \(n\)._  
Proof. : First, we note that checking for Condition (1) can be accomplished in time polynomial in \(n\) by simply inspecting the degree of every vertex in \(G[S_{R}\cup T_{A}]\). The total number of cycles satisfying condition (2) is linear in the number of degree-two vertices in \(G[S_{R}\cup T_{A}]\). Therefore, we can check for Condition (2) in time polynomial in \(n\) by a simple breadth-first search starting from every degree-two vertex in \(G[S_{R}\cup T_{A}]\). If \(G[S_{R}\cup T_{A}]\) has a vertex \(v\in S_{R}\) of degree zero, we let \(S^{\prime}\) denote the vertex cover obtained by simply removing \(v\) from \(S\). It is easy to see that the reconfiguration sequence from \(S\) to \(S^{\prime}\) is a zero-bounded prefix and can be found in time polynomial in \(n\). Similarly, if \(G[S_{R}\cup T_{A}]\) has a vertex \(v\in S_{R}\) of degree one, we let \(S^{\prime}\) denote the node obtained by the addition of the single vertex in \(N_{G[S_{R}\cup T_{A}]}(v)\) followed by the removal of \(v\).