# Expansion Lemma--Variations and Applications to Polynomial-Time Preprocessing
## 4 (Basic) Expansion Lemma and Applications
### Cluster Vertex Deletion  
The cluster vertex deletion problem can be formulated as a 3-hitting set (see Box 6 with \(d=3\)) problem with \(U=V(G)\) and \(\mathcal{F}\) being the vertex sets of all induced paths on three vertices (\(P_{3}\)s) of \(G\). Abu-Khzam [31] obtained a kernel with \(\mathcal{O}(k^{2})\) elements for the 3-hitting set. This kernel can be adapted to obtain kernels with \(\mathcal{O}(k^{2})\) vertices for cluster vertex deletion. Fomin et al. [37] obtained a kernel with \(\mathcal{O}(k^{5/3})\) vertices using Lemma 3 and more sophisticated techniques. We will see a brief overview of this kernel here. **Bounding the number of cliques. ** We give a simple argument to show how Lemma 3 can be used to bound the number of cliques to \(6k\). First, find a maximal collection \(\mathcal{P}\) of the vertex disjoint \(P_{3}\) in \(G\). If \(|\mathcal{P}|>k\), we return a no-instance as there is no optimal cluster vertex deletion set with a size of, at most, \(k\). Otherwise, set \(S\) as the subset of vertices in \(\mathcal{P}\). Note that \(|S|\leq 3k\). We use an auxiliary bipartite graph \(Q\) with \(S\) on one side and components (cliques) of \(G-S\) on the other side. Add an edge between a vertex \(u\in S\) and a component \(D\) in \(G-S\) if \(u\) has a neighbor in \(D\). Remove isolated cliques, if any. If the number of remaining cliques is more than \(6k\), then the conditions are satisfied for Lemma 3 with \(q=2\). This provides a head \(H\subseteq S\) and a crown \(C\), which is a subset of components in \(G-S\), such that there is a 2-expansion from \(H\) to \(C\) and \(N_{Q}(C)\subseteq H\). The reduction rule, similar to that of vertex cover, includes all of \(H\) into the solution, removes \(H\) and the components of \(C\), and drops \(k\) by \(|H|\). This is because it is easy to show that for any optimal solution \(X\), the set \(X^{\prime}=X\setminus(H\cup C)\cup H\) is also an optimal solution. The 2-expansion gives a collection of \(|H|\) disjointed \(P_{3}\)s that any solution needs to hit. Hence, \(|X^{\prime}|\leq|X|\). Then they use that \(N_{Q}(C)\subseteq H\) and that the graph on \(C\) is a cluster graph to claim that \(X^{\prime}\) is indeed a solution. This is because all \(P_{3}\)s containing vertices in components of \(C\) have to contain a vertex in \(H\), and these are covered by \(X^{\prime}\). Thus, the total number of cliques in \(G-S\) is bounded by \(6k\). **A marking procedure and a weak form of crown decomposition. ** After bounding the number of cliques in \(G-S\) by \(6k\), the authors [37] performed a marking procedure; this procedure involved associating an edge in \(G-S\) with each vertex in \(S\), such that exactly one endpoint of the edge is adjacent to that vertex. If \(k+1\) edges are associated with a vertex in \(S\), it can be concluded that this vertex must be in the solution as it is the intersection of the \(k+1\)\(P_{3}\) and reduces the instance accordingly. Otherwise, if \(k^{2/3}\) vertices of \(S\) roughly have \(k^{2/3}\) edges associated with them, call the run'successful' and mark and delete these vertices. This marking procedure is repeated until a successful run is obtained. Let \(U\) be the set of all marked vertices and \(M\) be the set of endpoints of the edges marked in the unsuccessful final run. Let \(L=S\setminus U\). The sets \(U,V(G)\setminus S\), and \(L\) can be viewed as a weak form of the crown decomposition with \(U\) being the head, \(V-S\) being the crown, and \(L\) being the body. When the crown decomposition is applied to obtain kernels, usually it can be concluded that there is a cluster vertex deletion set that contains all of the head, none of the crown, and all of the edges of the crown within the head. Similarly, in the weak crown decomposition, it can be concluded that _most_ of the vertices of the head \(U\) go into a solution, _almost none_ of the vertices of the crown \(V(G)\setminus S\) is in the solution, and _almost all_ of the edges from \(V(G)\setminus S\) are within \(U\).