# Expansion Lemma--Variations and Applications to Polynomial-Time Preprocessing
## 5 Recent Developments
### Stronger Expansion Lemma and Double Expansion Lemma  
Fomin et al. [37] defined the following stronger notion of a \(q\)-expansion. Let \(G=(V=A\uplus B,E)\) be a bipartite graph. Let \(q>0\) be an integer, \(\hat{A}\subseteq A\), and \(\hat{B}\subseteq B\). We say that there is a _stronger \(q\)-expansion_ of \(\hat{A}\) into \(\hat{B}\) if for all subsets \(X\subseteq\hat{A}\), we have \(|N_{G}(X)\cap\hat{B}|\geq q|X|\). Using this notion, they prove the following version of the expansion lemma, which does not need the conditions that \(|B|\geq q|A|\) or that there are no isolated vertices in \(B\). **Lemma 5** (Stronger Expansion Lemma [37]): _Let \(q\) be a positive integer, and \(G=(V=A\uplus B,E)\) be a bipartite graph. Then there exist (possibly empty) sets \(\hat{A}\subseteq A\) and \(\hat{B}\subseteq B\) such that_  
1. \(\hat{A}\) _has a stronger_ \(q\)_-expansion into_ \(\hat{B}\)_,_
2. \(N_{G}(\hat{B})\subseteq\hat{A}\)_, and_
3. \(|B\setminus\hat{B}|\leq q|A\setminus\hat{A}|\)_._  
_Moreover, the sets \(\hat{A}\) and \(\hat{B}\) can be computed in polynomial time. See Figure 2 for an illustration with \(q=2\)._  
This lemma is different from Lemma 3 as it does not require that \(|B|\geq q|A|\) and there are no isolated vertices in \(B\). Moreover, note that this lemma does not demand that \(\hat{A}\) and \(\hat{B}\) must be non-empty. If \(\hat{B}=\emptyset\) for some graph \(G\), then \(\hat{A}=\emptyset\) as there is a stronger \(q\)-expansion from \(\hat{A}\) to \(\hat{B}\). Moreover, since \(|B\setminus\hat{B}|\leq q|A\setminus\hat{A}|\), we have \(|B|\leq q|A|\). Therefore, if \(|B|>q|A|\), then \(\hat{B}\
eq\emptyset\). Note that in Lemma 3 (expansion lemma), \(|Y|=q|X|\). However, in a stronger expansion lemma, it could be that \(|\hat{B}|>q|\hat{A}|\). The intuition in applying a stronger expansion lemma for a problem instance is that some vertices of \(\hat{B}\) could be safely eliminated from the input graph. Note that since \(|B\setminus\hat{B}|\leq q|A\setminus\hat{A}|\), to bound the size of \(B\) as a function of \(|A|\), we might need to remove some of the vertices of \(\hat{B}\). Observe that for every \(u\in\hat{A}\), there is at least \(q\) edges incident. Thus, by keeping exactly \(q|\hat{A}|\) vertices in \(\hat{B}\), the property of a \(q\)-expansion from \(\hat{A}\) is maintained. Thus, the other vertices from \(\hat{B}\), which only has neighbors to \(\hat{A}\), could be deleted. The following problem Arc Disjoint 4-Cycle Packing provides an intuition to use the above lemma. Babu et al. [58] first proved that for every fixed \(r\geq 3\), Arc Disjoint \(r\)-Cycle Packing is NP-complete in directed graphs of girth \(r\), and this NP-completeness result holds for every \(r\geq 4\) when the input graph is bipartite. After that, they provide a kernel with \(\mathcal{O}(k^{2})\) vertices and \(\mathcal{O}(k^{3})\) arcs for \(r=4\), i.e., for the Arc Disjoint 4-Cycle Packing (see Box 28) problem using a stronger expansion lemma (Lemma 5). A brief summary of the kernelization algorithm by Babu et al. [58] works as follows. 1. Initially, the authors apply some preprocessing rules to the input graph \(D\) and ensure that every arc \((u,v)\) of \(D\) is contained in at most \((4k-4)\) distinct 4-cycles, the pairwise intersection of which is \(\{u,v\}\). Figure 2: An illustration of Lemma 5 with \(q=2\). Let \(\mathcal{X}\) be a collection of the maximal set of 4-cycles, such that for every pair of 4-cycles in \(\mathcal{X}\), there is at most one common vertex. The authors prove that if \(|\mathcal{X}|>16k^{2}\), then the input is a YES instance. 3. So, it can be assumed that \(|\mathcal{X}|\leq 16k^{2}\). Let \(\mathcal{P}\) be the set of all 3 paths that are contained in the 4-cycle in \(\mathcal{X}\). As \(|\mathcal{X}|\leq 16k^{2}\), \(|\mathcal{P}|\) is \(\mathcal{O}(k^{2})\). What is left is to bind the number of vertices in \(V(D)\setminus V(\mathcal{P})\). 4.