# Vertex Cover Reconfiguration and Beyond +
## 5 Polynomial-Time Algorithms  
In this section, we present a characterization of instances of the VCR problem solvable in time polynomial in \(n\), and apply this characterization to trees, graphs with no even cycles (as subgraphs) and to cactus graphs (with some additional restrictions). We show how to find reconfigurationsequences of the shortest possible length and therefore ignore the parameter \(\ell\). Unless stated otherwise, reconfiguration sequences are represented as ordered sequences of vertex covers or nodes in the reconfiguration graph. Given two vertex covers of \(G\), \(A\) and \(B\), a reconfiguration sequence \(\beta\) from \(A\) to some vertex cover \(A^{\prime}\) is a \(c\)-bounded prefix of a reconfiguration sequence \(\alpha\) from \(A\) to \(B\), if and only if all of the following conditions hold:  
1. \(|A^{\prime}|\leq|A|\);
2. For every node \(A^{\prime\prime}\) in \(\beta\), \(|A^{\prime\prime}|\leq|A|+c\);
3. For every node \(A^{\prime\prime}\) in \(\beta\), \(A^{\prime\prime}\) is obtained from its predecessor by either the removal or the addition of a single vertex in the symmetric difference of the predecessor and \(B\);
4. No vertex is touched more than once in the course of \(\beta\). We write \(A\xleftrightarrow{c.B}A^{\prime}\) when such a \(c\)-bounded prefix exists. Given two vertex covers \(S\) and \(T\) of \(G\), if \(G\) has a vertex cover \(S^{\prime}\) such that \(S\xleftrightarrow{c.T}S^{\prime}\), then \(S\xleftrightarrow{d.T}S^{\prime}\) for all \(d>c\). Given two vertex covers \(S\) and \(T\) of \(G\) and two positive integers \(k\) and \(c\) such that \(|S|,|T|\leq k\), a reconfiguration sequence \(\alpha\) of length \(|S_{R}|+|T_{A}|=|S\Delta T|\) from \(S\) to \(T\) exists if:  
1. \(|S|\leq k-c\);
2. \(|T|\leq k-c\); and
3. For any two vertex covers \(A\) and \(B\) of \(G\) such that \(|A|\leq k-c\) and \(|B|\leq k-c\), either \(A\xleftrightarrow{c.B}A^{\prime}\) or \(B\xleftrightarrow{c.A}B^{\prime}\), where \(A^{\prime}\) and \(B^{\prime}\) are vertex covers of \(G\). Moreover, if \(c\)-bounded prefixes can be found in time polynomial in \(n\), then \(\alpha\) can be found in time polynomial in \(n\). Proof. : We prove the lemma by induction on \(|S\Delta T|\). When \(|S\Delta T|=0\), \(S\) is equal to \(T\), and the claim holds trivially since \(|\alpha|=0\). When \(|S\Delta T|>0\), we know that either \(S\xleftrightarrow{c.T}S^{\prime}\) or \(T\xleftrightarrow{c.S}T^{\prime}\). Without loss of generality, we assume \(S\xleftrightarrow{c.T}S^{\prime}\) and let \(\beta\) denote the \(c\)-bounded prefix from \(S\) to \(S^{\prime}\). From Definition 1, we know that the size of every node in \(\beta\) is no greater than \(|S|+c\leq k\). Therefore, the maximum allowed capacity constraint is never violated. Since \(|S^{\prime}|\leq|S|\) (Definition 1), by the induction hypothesis, there exists a reconfiguration sequence from \(S^{\prime}\) to \(T\) whose length is \(|S^{\prime}\Delta T|\). By appending the reconfiguration sequence from \(S^{\prime}\) to \(T\) to the reconfiguration sequence from \(S\) to \(S^{\prime}\), we obtain a reconfiguration sequence \(\alpha\) from \(S\) to \(T\). To show that \(|\alpha|=|S\Delta T|\), it suffices to show that \(|\beta|+|S^{\prime}\Delta T|=|S\Delta T|\). We know that no vertex is touched more than once in \(\beta\), and every touched vertex belongs to \(S\Delta T\) (Definition 1). We let \(H\subseteq S\Delta T\) denote the set of touched vertices in \(\beta\), and we subdivide \(H\) into two sets \(H_{S}=H\cap S=H\cap S_{R}\) and \(H_{T}=H\cap T=H\cap T_{A}\). It follows that \(|\beta|=|H_{S}|+|H_{T}|\) and \(|S^{\prime}\Delta T|=|S_{R}\setminus H_{S}|+|T_{A}\setminus H_{T}|\). Therefore, \(|\beta|+|S^{\prime}\Delta T|=|H_{S}|+|H_{T}|+|S_{R}\setminus H_{S}|+|T_{A} \setminus H_{T}|=|S_{R}|+|T_{A}|=|S\Delta T|\) as needed. When \(c\)-bounded prefixes can be found in time polynomial in \(n\), the proof gives an algorithm for constructing the full reconfiguration sequence from \(S\) to \(T\) in time polynomial in \(n\).