# Vertex Cover Reconfiguration and Beyond +
## 2 Preliminaries  
For general graph theoretic definitions, we refer the reader to the book of [PERSON] [15]. Unless otherwise stated, we assume that each graph \(G\) is a simple undirected graph with vertex set \(V(G)\) and edge set \(E(G)\), where \(|V(G)|=n\) and \(|E(G)|=m\). The open neighbourhood of a vertex \(v\) is denoted by \(N_{G}(v)=\{u\mid uv\in E(G)\}\) and the closed neighbourhood by \(N_{G}[v]=N_{G}(v)\cup\{v\}\). For a set of vertices \(A\subseteq V(G)\), we define \(N_{G}(A)=\{v\
ot\in A\mid uv\in E(G),u\in A\}\) and \(N_{G}[A]=N_{G}(A)\cup A\). The subgraph of \(G\) induced by \(A\) is denoted by \(G[A]\), where \(G[A]\) has vertex set \(A\) and edge set \(\{uv\in E(G)\mid u,v\in A\}\). A walk of length \(q\) from \(v_{0}\) to \(v_{q}\) in \(G\) is a vertex sequence \(v_{0},\ldots,v_{q}\) such that, for all \(i\in\{0,\ldots,q-1\}\), \(v_{i}v_{i+1}\in E(G)\). It is a path if all vertices are distinct and a cycle if \(q\geq 3\), \(v_{0}=v_{q}\), and \(v_{0},\ldots,v_{q-1}\) is a path. A matching \(\mathcal{M}(G)\) on a graph \(G\) is a set of edges of \(G\) such that no two edges share a vertex; we use \(V(\mathcal{M}(G))\) to denote the set of vertices incident to edges in \(\mathcal{M}(G)\). A set of vertices \(A\subseteq V(G)\) is said to be saturated by \(\mathcal{M}(G)\) if \(A\subseteq V(\mathcal{M}(G))\). To avoid confusion, we refer to nodes in reconfiguration graphs, as distinguished from vertices in the input graph. We denote an instance of the vertex cover reconfiguration problem by \((G,S,T,k,\ell)\), where \(G\) is the input graph, \(S\) and \(T\) are the source and target vertex covers, respectively, \(k\) is the maximum allowed capacity and \(\ell\) is an upper bound on the length of the reconfiguration sequence we seek. By a slight abuse of notation, we use upper case letters to refer to both a node in the reconfiguration graph, as well as the corresponding vertex cover. For any node \(S\in V(\mathcal{R}_{\mathsf{VC}}(G,0,k))\), the quantity \(k-|S|\) corresponds to the available capacity at \(S\). We partition \(V(G)\) into the sets \(C_{ST}=S\cap T\) (vertices common to \(S\) and \(T\)), \(S_{R}=S\setminus C_{ST}\) (vertices to be removed from \(S\) in the course of reconfiguration), \(T_{A}=T\setminus C_{ST}\) (vertices to be added to form \(T\)) and \(O_{ST}=V(G)\setminus(S\cup T)=V(G)\setminus(C_{ST}\cup S_{R}\cup T_{A})\) (all other vertices). To simplify notation, we sometimes use \(G_{\Delta}\) to denote the graph induced by the vertices in the symmetric difference of \(S\) and \(T\), i.e., \(G_{\Delta}=G[S\Delta T]=G[S_{R}\cup T_{A}]\). We say a vertex is touched in the course of a reconfiguration sequence from \(S\) to \(T\) if \(v\) is either added or removed at least once. We say a vertex \(v\), in a vertex cover \(S\), is removable if and only if \(v\in S\) and \(N_{G}(v)\subseteq S\). Proposition 1: _For any graph \(G\) and any two vertex covers \(S\) and \(T\) of \(G\), \(G_{\Delta}=G[S_{R}\cup T_{A}]\) is bipartite. Moreover, there are no edges between vertices in \(S_{R}\cup T_{A}\) and vertices in \(O_{ST}\)._  
Proof: None of the vertices in \(S_{R}\) are included in \(T\). Since \(T\) is a vertex cover of \(G\), each edge of \(G\) must have an endpoint in \(T\), and hence, \(G[S_{R}]\) must be an independent set. Similar arguments apply to \(G[T_{A}]\) and to show that there are no edges between vertices in \(S_{R}\cup T_{A}\) and vertices in \(O_{ST}\). Proposition 2: _For a graph \(G\) and any two vertex covers \(S\) and \(T\) of \(G\), any vertex in \(S_{R}\cup T_{A}\) must be touched an odd number of times and any vertex not in \(S_{R}\cup T_{A}\) must be touched an even number of times in any reconfiguration sequence of length at most \(\ell\) from \(S\) to \(T\). Moreover, any vertex can be touched at most \(\ell-|S_{R}\cup T_{A}|+1\) times._  
Throughout this work, we implicitly consider the vertex cover reconfiguration problem as a parameterized problem with \(\ell\) as the parameter.