# Expansion Lemma--Variations and Applications to Polynomial-Time Preprocessing
## Box 30
### Additive Expansion Lemma  
Koana et al. [61] introduced the following variant of the expansion and the expansion lemma. **Definition 12** (\(q\)-Additive Expansion, [61]). : _Let \(G=(V=A\uplus B,E)\) be a bipartite graph and \(q\) be a positive integer. Then, \(G\) is said to have a \(q\)-additive expansion from \(A\) into \(B\) if for every \(B^{\prime}\subseteq B\) of size \(q\), there is a matching saturating \(A\) in \(G[A,B\setminus B^{\prime}]\)._  
For completeness, we give proof of the following proposition that is stated in [61]. **Proposition 3**. : _Let \(G=(V=A\uplus B,E)\) be a bipartite graph. There is a \(q\)-additive expansion from \(A\) into \(B\) if and only if for every nonempty \(X\subseteq A\), \(|N(X)|\geq|X|+q\)._  
Proof. : We will prove this using Hall's theorem. Consider the forward direction (\(\Rightarrow\)) first. Suppose that \(G\) has a \(q\)-additive expansion from \(A\) to \(B\). Then, for every \(B^{\prime}\subseteq B\) of size \(q\), there is a matching saturating \(A\) in \(G^{\prime}=G[A,B\setminus B^{\prime}]\). It means that for every non-empty \(X\subseteq A\), \(|N(X)\setminus B^{\prime}|\geq|X|\). Consider the value of \(|N_{G}(X)|\). If \(|N_{G}(X)|<|X|+q\), then consider a set of an arbitrary set \(\hat{B}\) of \(q\) vertices from \(N_{G}(X)\). Clearly, \(\hat{B}\subseteq B\) has \(q\) vertices. However, then in the graph \(\hat{G}=G[A,B\setminus\hat{B}]\), for the same set \(X\subseteq A\), it holds that \(|N_{G}(X)|<|X|\). Then it leads to a contradiction that there is a matching saturating \(A\) in \(\hat{G}\). Let us now prove the backward direction (\(\Leftarrow\)). Suppose that for every nonempty \(X\subseteq A\), \(|N(X)|\geq|X|+q\). We have to justify that for every \(B^{\prime}\subseteq B\) of size \(q\), there is a matching saturating \(A\) in \(G[A,B\setminus B^{\prime}]\). Suppose that for some \(B^{*}\subseteq B\) of size \(q\), there is no matching saturating \(A\) in \(G^{*}=G[A,B\setminus B^{*}]\). Then, by Proposition 1 (Hall's theorem), there is \(X\subseteq A\), such that \(|N_{G^{*}}(X)|<|X|\). As \(B^{*}\) is of size \(q\), then in \(G\) also, it holds that \(|N_{G}(X)|<|X|+q\). This contradicts the premise, which completes the proof of the observation. Now, we state the _additive expansion lemma_ and give a short explanation of how it has been used to provide an improved kernel for partial vertex cover. **Lemma 10** (Additive Expansion Lemma [61]). : _Let \(q\geq 1\) and \(G=(V=A\uplus B,E)\) be a bipartite graph. If \(|B|>q|A|\) and there is no isolated vertex in \(B\), then there exists nonempty \(\hat{A}\subseteq A\) and \(\hat{B}\subseteq B\) such that_  
* _There is a_ \(q\)_-additive expansion of_ \(\hat{A}\) _into_ \(\hat{B}\)_; and_
* _No vertex of_ \(\hat{B}\) _has the neighbor outside_ \(\hat{A}\)_, i.e.,_ \(N(\hat{B})\subseteq\hat{A}\)_._  
First, the authors [61] provide a kernel with \((\ell+2)(k+\ell)\) vertices that use the expansion lemma (Lemma 3). It works as follows. * First, they consider the LP formulation of Vertex Cover. By Nemhauser and Trotter [62], there is a fractional optimal solution for the LP formulation of Vertex Cover such that all vertices are assigned values of either \(0\), \(1\), or \(1/2\). * Let \(V_{0},V_{1},V_{1/2}\) denote the vertices that are assigned values \(0\), \(1\), \(1/2\), respectively. If \(|V_{1}|+|V_{1/2}|\geq k+\ell+1\), then the instance is a no-instance. * Otherwise, they construct an auxiliary bipartite graph, and apply the expansion lemma to obtain a kernel with \((\ell+2)(k+\ell)\) vertices. After that, they give a proof using the additive expansion lemma (Lemma 10), a kernel with \((\ell^{\prime}+1)(k+\ell)\) vertices can be obtained, such that \(\ell^{\prime}=\max\{\ell,1\}\). The rest of the proof for the problem defined in Box 34 has similar structures, but a crucial difference is that they use Lemma 10 instead of Lemma 3.