# Vertex Cover Reconfiguration and Beyond +
## 5 Polynomial-Time Algorithms
### Trees  
Vertex cover reconfiguration restricted to trees can be solved in time polynomial in \(n\). Proof. : We let \((G,S,T,k,\ell)\) be an instance of vertex cover reconfiguration. The proof proceeds in two stages. We start by showing that when \(G\) is a tree and \(S\) and \(T\) are of size at most \(k-1\), we can always find one-bounded prefixes \(S\xleftrightarrow{1,T}S^{\prime}\) or \(T\xleftrightarrow{1,S}T^{\prime}\) in time polynomial in \(n\). Therefore, we can apply Lemma 2 with \(c=1\) to find a reconfiguration sequence of length \(|S\Delta T|\) from \(S\) to \(T\) in time polynomial in \(n\). In the second part of the proof, we show how to handle the remaining cases where \(S\), \(T\) or both \(S\) and \(T\) are of a size greater than \(k-1\). First, we note that every forest either has a degree-zero or a degree-one vertex. Hence, trees and forests are one-degenerate graphs. Since \(G\) is a tree, \(G[S_{R}\cup T_{A}]\) is a forest and is therefore one-degenerate. To find one-bounded prefixes in \(G[S_{R}\cup T_{A}]\), it is enough to find a vertex of degree at most one, which can clearly be done in time polynomial in \(n\): For any two vertex covers \(S\) and \(T\) of a tree \(G\) such that \(S,T\leq k-1\), we can always find a vertex \(v\in S_{R}\cup T_{A}\) having degree at most one in \(G[S_{R}\cup T_{A}]\). The existence of \(v\) guarantees the existence of a one-bounded prefix from either \(S\) to some vertex cover \(S^{\prime}\) or from \(T\) to some vertex cover \(T^{\prime}\). When \(v\in S_{R}\) and \(|N_{G[S_{R}\cup T_{A}]}(v)|=0\), we have \(S\xleftrightarrow{0,T}S^{\prime}\), since \(S^{\prime}\) is obtained from \(S\) by simply removing \(v\). When \(v\in S_{R}\) and \(|N_{G[S_{R}\cup T_{A}]}(v)|=1\), we have \(S\xleftrightarrow{1,T}S^{\prime}\), since \(S^{\prime}\) is obtained from \(S\) by first adding the unique neighbour of \(v\) and then removing \(v\). Similar arguments hold when \(v\in T_{A}\). Therefore, combining Lemma 2 and the fact that \(G[S_{R}\cup T_{A}]\) is one-degenerate, we know that if \(|S|\leq k-1\) and \(|T|\leq k-1\), a reconfiguration sequence of length \(|S_{R}|+|T_{A}|\) from \(S\) to \(T\) can be found in time polynomial in \(n\). Furthermore, since the length of a reconfiguration sequence can never be less than \(|S_{R}|+|T_{A}|\), the reconfiguration sequence given by Lemma 2 is the shortest path from \(S\) to \(T\) in the reconfiguration graph. When \(S\) (or \(T\)) has size \(k\) and is minimal, then we have a no-instance, since neither removing, nor adding a vertex results in a \(k\)-vertex cover, and hence, \(S\) (or \(T\)) will be an isolated node in the reconfiguration graph, with no path to \(T\) (or \(S\)). When \(S\), \(T\) or both \(S\) and \(T\) are of size \(k\) and are non-minimal, there always exists a reconfiguration sequence from \(S\) to \(T\), since \(S\) and \(T\) can be reconfigured to solutions \(S^{\prime}\) and \(T^{\prime}\), respectively, of size less than \(k\), to which Lemma 2 can be applied. The only reconfiguration steps from \(S\) (or \(T\)) of size \(k\) are to subsets of \(S\) of size \(k-1\) (or to subsets of \(T\) of size \(k-1\)); the reconfiguration sequence obtained from Lemma 2 is thus a shortest path. Therefore, we can obtain a shortest path from \(S\) to \(T\) through a careful selection of \(S^{\prime}\) and \(T^{\prime}\). There are two cases to consider:  
**Case (1):**\(|S|=k\), \(|T|=k\), \(S\) is non-minimal and \(T\) is non-minimal. When both \(S\) and \(T\) are of size \(k\) and are non-minimal, then each must contain at least one removable vertex. Hence, by removing such vertices, we can transform \(S\) and \(T\) into vertex covers \(S^{\prime}\) and \(T^{\prime}\), respectively, of size \(k-1\). We let \(u\) and \(v\) be removable vertices in \(S\) and \(T\), respectively, and we set \(S^{\prime}=S\setminus\{u\}\) and \(T^{\prime}=T\setminus\{v\}\). 1.