# Expansion Lemma--Variations and Applications to Polynomial-Time Preprocessing
## Box 14 Cluster Vertex Deletion Problem.
### Other Deletion Problems  
In this section, we list some other deletion problems where the expansion lemma was used to obtain kernels. Here, \(d\) is a fixed integer. There have been several previous works on \(d\)-PVC with \(d=4,\ d=5\), etc. Cerveny and Suchy [38] provided parameterized algorithms for 4-PVC and 5-PVC (assign \(d=4\) and \(d=5\) respectively in Box 15). Later, Cerveny et al. [39] obtained a polynomial kernel for \(d\)-Path Vertex Cover with \(\mathcal{O}(k^{2})\) vertices for \(d=4\) and \(d=5\) using Lemma 3. They also obtained a polynomial kernel for \(d\)-Path Vertex Cover with \(k^{4}d^{\mathcal{O}(d)}\) vertices and edges for every fixed \(d\). **Box 15**. : \(d\)-Path Vertex Cover Problem. ```
\(d\)-Path Vertex Cover (\(d\)-PVC) Input:An undirected graph \(G=(V,E)\) and an integer \(k\). Parameter:\(k\) Question:Is there a set \(S\subseteq V(G)\) of, at most, \(k\) vertices, such that \(G-S\) has no path of length \(d\)? ```  
**Box 16**. : Vertex Cover parameterized by degree-2-modulator. Philip et al. [41] provided a kernel with \(\mathcal{O}(k^{2})\) vertices for Pathwidth-One Vertex Deletion. Cygan et al. [42] used Lemma 3 to give a simpler kernel with \(\mathcal{O}(k^{2})\) vertices for this above problem as defined in Box 17. **Box 17**. : Pathwidth-One Vertex Deletion Problem. **Input:**_An undirected graph \(G=(V,E)\) and an integer \(k\)._  
**Parameter:**_\(k\)._  
**Question:**_Is there a set \(S\subseteq V(G)\) of, at most, \(k\) vertices, such that \(G-S\) has a pathwidth of, at most, one?_  
Kim and Kwon [43] initiated the study of Block Graph Vertex Deletion problem from parameterized complexity perspective and provided a kernel with \(\mathcal{O}(k^{9})\) vertices. Later, Agrawal et al. [44] improved it by giving a kernel with \(\mathcal{O}(k^{4})\) vertices using Lemma 3. Jansen et al. [45] provided a kernel with \(\mathcal{O}(k^{161}\log^{58}k)\) edges for Chordal Vertex Deletion. Later, Agrawal et al. [46] improved their results using Lemma 3 into a kernel with \(\mathcal{O}(k^{12}\log^{2}k)\) edges. In addition, Agrawal et al. [46] used the notion of the _independence degree_ of a vertex to obtain this result. Misra et al. [47] initiated the study of the Even Cycle Transversal problem from a parameterized complexity perspective. They proved the problem to be FPT and gave a kernel with \(\mathcal{O}(k^{2})\) vertices. Their kernelization algorithm also uses Lemma 3 as a crucial tool to obtain such a kernel upper bound. Minch and van Leeuwen [48] provided a kernel with \(\mathcal{O}(k^{3})\) vertices for Out-Forest Vertex Deletion Set. Later, Agrawal et al. [49] used Lemma 3 to obtain an improved kernel with \(\mathcal{O}(k^{2})\) vertices. Misra et al. [50] studied the Independent Feedback Vertex Set problem from a parameterized complexity perspective. This problem is a variation of Feedback Vertex Set (defined in Box 13) with additional constraints imposed for the feedback vertex set. They use Lemma 3 to obtain a kernel with \(\mathcal{O}(k^{3})\) vertices and edges. A common theme for the problems Pathwidth-One Vertex Deletion (Box 17), Block Graph Vertex Deletion (Box 18), Chordal Vertex Deletion (Box 19), Even Cycle Transversal (Box 20), Out-Forest Vertex Deletion Set (Box 21), and Independent Feedback Vertex Set (Box 22) is that they all have some infinite cycles as forbidden subgraphs. The application of Lemma 3 (expansion lemma) for all of these problems is inspired by the application by Thomasse [6] for Feedback Vertex Set. The \(q\)-expansion from the lemma is used to identify sets of cycles that pairwise intersect in one or two vertices, which has to be hit by the solution. This is used to bind a degree measure for vertices \(v\) of \(G\) (the measure depends on the problem) by bounding the number of components associated with \(v\). **Box 18**. : Block Graph Vertex Deletion Problem.