# Vertex Cover Reconfiguration and Beyond +
## 3 Representing Reconfiguration Sequences  
There are multiple ways of representing a reconfiguration sequence between two vertex covers of a graph \(G\). In Sections 4 and 5, we focus on a representation that consists of an ordered sequence of vertex covers or nodes in the reconfiguration graph. Given a graph \(G\) and two vertex covers of \(G\), \(A_{0}\) and \(A_{j}\), we denote a reconfiguration sequence from \(A_{0}\) to \(A_{j}\) by \(\alpha=(A_{0},A_{1},\ldots,A_{j})\), where \(A_{i}\) is a vertex cover of \(G\) and \(A_{i}\) is obtained from \(A_{i-1}\) by either the removal or the addition of a single vertex from \(A_{i-1}\) for all \(0<i\leq j\). For any pair of consecutive vertex covers \((A_{i-1},\,A_{i})\) in \(\alpha\), we say \(A_{i}\) (\(A_{i-1}\)) is the successor (predecessor) of \(A_{i-1}\) (\(A_{i}\)). A reconfiguration sequence \(\beta=(A_{0},A_{1},\ldots,A_{i})\) is a prefix of \(\alpha=(A_{0},A_{1},\ldots,A_{j})\) if \(i<j\). In Section 6, we use the notion of edit sequences. We assume all vertices of \(G\) are labelled from one to \(n\), i.e., \(V(G)=\{v_{1},v_{2},\ldots,v_{n}\}\). We let \(\mathcal{E}_{\alpha}=\{a_{1},\ldots,a_{n}\}\) and \(\mathcal{E}_{r}=\{r_{1},\ldots,r_{n}\}\) denote the sets of addition markers and removal markers, respectively. An edit sequence \(\alpha\) is an ordered sequence of elements obtained from the full set of markers \(\mathcal{E}=\mathcal{E}_{\alpha}\cup\mathcal{E}_{r}\), where \(a_{i}\) stands for the addition of vertex \(v_{i},r_{j}\) stands for the removal of vertex \(v_{j}\) and \(1\leq i,j\leq n\). The length of \(\alpha\), \(|\alpha|\), is equal to the total number of markers in \(\alpha\). We let \(\alpha[p]\in\mathcal{E}\), \(1\leq p\leq|\alpha|\), denote the marker at position \(p\) in \(\alpha\). We say \(\beta\) is a segment of \(\alpha\) whenever \(\beta\) consists of a subsequence of \(\alpha\) with no gaps. The length of a segment is defined as the total number of markers it contains. We use the notation \(\alpha[p_{1},p_{2}]\), \(1\leq p_{1},\ p_{2}\leq|\alpha|\)to denote the segment starting at position \(p_{1}\) and ending at position \(p_{2}\). Two segments \(\beta\) and \(\beta^{\prime}\) are consecutive whenever \(\beta^{\prime}\) occurs later than \(\beta\) in \(\alpha\) and there are no gaps between \(\beta\) and \(\beta^{\prime}\). For any pair of consecutive segments \(\beta\) and \(\beta^{\prime}\) in \(\alpha\), we say \(\beta^{\prime}\) (\(\beta\)) is the successor (predecessor) of \(\beta\) (\(\beta^{\prime}\)). Given an edit sequence \(\alpha\), a segment \(\beta\) of \(\alpha\) is a maximal addition segment if \(\beta\) is a maximal subsequence of \(\alpha\) consisting of only addition markers and no gaps. Similarly, \(\beta\) is a maximal removal segment if \(\beta\) is a maximal subsequence of \(\alpha\) consisting of only removal markers and no gaps. We now discuss how edit sequences relate to reconfiguration sequences. Given a graph \(G\) and an edit sequence \(\alpha\), we use \(V(\alpha)\) to denote the set of vertices touched in \(\alpha\), i.e., \(V(\alpha)=\{v_{i}\mid a_{i}\in\alpha\lor r_{i}\in\alpha\}\). We let \(V(S,\alpha)\) denote the set of vertices obtained after executing all reconfiguration steps in \(\alpha\) on \(G\) starting from some vertex cover \(S\) of \(G\). We say \(\alpha\) is valid whenever every set \(V(S,\alpha[1,p])\), \(1\leq p\leq|\alpha|\), is a vertex cover of \(G\), and we say \(\alpha\) is invalid otherwise. Note that even if \(|S|\leq k\), \(\alpha\) is not necessarily a walk in the reconfiguration graph \(\mathcal{R}_{\mathsf{VC}}(G,0,k)\), as \(\alpha\) might violate the maximum allowed capacity constraint \(k\). Hence, we let \(\mathsf{cap}(\alpha)=\max_{1\leq p\leq|\alpha|}(|V(S,\alpha[1,p])|)\), and we say \(\alpha\) is tight whenever it is valid and \(\mathsf{cap}(\alpha)\leq k\).