# Expansion Lemma--Variations and Applications to Polynomial-Time Preprocessing
## 5 Recent Developments
### Stronger Expansion Lemma and Double Expansion Lemma
The authors construct an auxiliary bipartite graph \(H\) with bipartitions \(A\) and \(B\) where \(A=\mathcal{P}\) and \(B=V(D)\setminus V(\mathcal{P})\). For \(u\in B\) and \(\{x,y,z\}\in\mathcal{P}\), there is an edge in \(H\) if and only if \(\{x,y,z,u\}\) is a 4-cycle in \(D\). 5. One can now apply Lemma 5 with \(q=1\) and obtain a stronger 1-expansion with sets \(\hat{A}\subseteq A\) and \(\hat{B}\subseteq B\). It ensures that \(|B\setminus\hat{B}|\leq|A\setminus\hat{A}|\). Let \(\hat{M}\subseteq E(\hat{A},\hat{B})\) be the set of edges of \(H\) such that every vertex of \(\hat{A}\) is incident to exactly one vertex of \(\hat{B}\) and every vertex of \(\hat{B}\) is incident to exactly one vertex of \(\hat{A}\). 6. Finally, the authors apply a reduction rule that deletes the set of vertices from \(\hat{B}\), which is not saturated by \(\hat{M}\). The 4-cycles that these vertices are part of can be covered by picking one of the vertices from the corresponding 3-paths in \(\hat{A}\). The matching \(M\) ensures that there exists a 4-cycle for each 3-path in \(\hat{A}\). Thus, the reduction rule is safe. 7. The reduction rule is no longer applicable when the set of vertices from \(\hat{B}\) that is not saturated by \(\hat{M}\) is empty. In this case, we have \(|B|=|B\setminus\hat{B}|+|\hat{B}|\leq|A\setminus\hat{A}|+|\hat{A}|=|A|\), which is \(\mathcal{O}(k^{2})\). Thus, we obtain a kernel with \(\mathcal{O}(k^{2})\) vertices. **Box 28**. : Arc Disjoint \(r\)-Cycle Packing Problem. [style  
A double expansion lemma was used in Feedback Vertex Set in Tournaments to give an improved kernel. We formally define the problem below. Feedback Vertex Set in Tournaments can be cast as a 3-hitting set problem (see Box 6), and hence its kernel can be adapted to obtain a kernel with \(\mathcal{O}(k^{2})\) vertices. Fomin et al. [37] used Lemma 6 (double expansion lemma) to obtain a kernel with \(\mathcal{O}(k^{3/2})\) vertices. We give a sketch of the algorithm below. As hitting directed cycles in a tournament is equivalent to hitting directed triangles in a tournament, a 3-approximation algorithm follows for Feedback Vertex Set in Tournaments. However, a set \(S\) has a size of, at most, \(7k/3\) can also be obtained due to Minch et al. [59] such that \(D-S\) is acyclic. We call an arc \((x,y)\in A\) as _strong arc_ if \((x,y)\) is part of at least \(k+2\) triangles with the other endpoints of the triangles from \(S\). In this case, one of \(x\) and \(y\) has to be in every solution. Since \(D-S\) is acyclic, its vertices have a topological ordering. We can extend this to an ordering of vertices of \(D\) by adding vertices in \(S\) such that it minimizes certain \"conflicts\". In this ordering, we can then argue that the vertices of every triangle in \(D\) that do not contain a strong arc are within \(7k\) distance from each other in the ordering. Hence, these triangles are, in a sense _local_. The problem boils down to simultaneously hitting strong arcs and the local triangles. This is achieved by using Lemma 6 by constructing a _global_ graph corresponding to the strong arcs and _local_ graphs for the local triangles. First, the vertices of \(D-S\) are broken into groups of size \(100k\) according to the topological ordering. Then, the authors [37] look at the first \(p=4\sqrt{k}\) of such groups \(Y_{1},Y_{2},\ldots,Y_{p}\), and discard the first and last \(7k+1\) vertices of each to form intervals \(Y_{1}^{\prime},Y_{2}^{\prime},\ldots,Y_{p}^{\prime}\). For \(i\in[p]\), let \(S_{i}\) be the set of vertices in \(S\) that are placed within \(Y_{i}^{\prime}\) in the ordering of \(V(D)\). Note that the vertices of any local triangle containing a vertex in \(Y_{i}^{\prime}\) are contained in the set \(S_{i}\cup Y_{i}\). Then each interval \(Y_{i}^{\prime}\), \(i\in[p]\) can be divided into \(q\) subintervals \(Y_{i,1},Y_{i,2},\ldots,Y_{i,q}\), each of size \(3\sqrt{k}\). Next, they define a global bipartite graph \(G\) with bipartition \(S\uplus\{Y_{i,j}:i\in[p],j\in[q]\}\) and strong arcs.