# Expansion Lemma--Variations and Applications to Polynomial-Time Preprocessing
## 4 (Basic) Expansion Lemma and Applications
### \(p\)-Component Order Connectivity  
In \(p\)-component order connectivity, the goal is to find a subset of \(k\) vertices in a given graph, such that every component of the remaining graph has a size of, at most, \(p\) for a fixed integer of \(p\). More formally, note that when \(p=1\), \(G-S\) is an independent set. Thus, \(p\)-component order connectivity is a generalization of vertex cover (see Box 1). We explain how a kernel with \(\mathcal{O}(p^{3}k)\) vertices can be obtained for this problem. Note that improved kernels are available for this problem using stronger versions of the expansion lemma (see Section 5), we give an \(\mathcal{O}(k^{3}p)\) kernel to illustrate a simple application of Lemma 3. The results in the literature are improvements of this result using some new tools (available in Section 5).  
We can obtain an approximate solution \(X\) of, at most, \((p+1)k\) by repeatedly finding connected subsets of size \(p+1\), adding it to \(X\) and deleting it from \(G\) (if \(|X|>(p+1)k\), then it is a no-instance). We can safely remove all components in \(G-X\) with a size of, at most, \(p\), as its vertices cannot be part of any optimal solution. We now use an auxiliary bipartite graph \(Q\) with \(X\) on one side and components of \(G-X\) on the other side. We add an edge between a vertex \(u\in X\) and a component \(D\) in \(G-X\) if \(u\) has a neighbor in \(D\). If the number of components in \(G-X\) is more than \(p(p+1)k\), then the conditions for Lemma 3 are satisfied with \(q=p\). Thus, we obtain a head \(H\subseteq X\) and a crown \(C\), which is a subset of connected components in \(G-X\), such that there is a \(p\)-expansion of \(H\) into \(C\) and \(N_{Q}(C)\subseteq H\). Our reduction rule, similar to that of the vertex cover, includes all of \(H\) into the solution, removes \(H\) and components of \(C\) and drops \(k\) by \(|H|\). We again aim to claim that for an optimal solution \(S\), the set \(S^{\prime}=(S\setminus(H\cup C))\cup H\) is also an optimal solution. The \(p\)-expansion gives a collection of \(|H|\) disjointed connected sets of sizes \((p+1)\) that any solution needs to hit. Hence, \(|S^{\prime}|\leq|S|\). We use that \(N_{Q}(C)\subseteq H\) and the graph on \(C\) contains only components with a size of, at most, \(p\) to claim that \(S^{\prime}\) is indeed a solution. This is because all of the connected sets of sizes more than \(p\) where vertices in components of \(C\) are part of must contain a vertex in \(H\). These are hit by \(S^{\prime}\). Thus, the number of connected components in \(G-X\) is bounded by \(p(p+1)k\). Each of these components has a size of, at most, \(p\). Hence, we obtain a kernel with \(\mathcal{O}(p^{3}k)\) vertices for this problem (defined in Box 12).  
Figure 1: An illustration of Lemma 3 with \(q=2\).  
\(p\)-Component Order Connectivity  
**Input:**_Graph \(G\) and an integer \(k\)._  
**Parameter:**_k._  
**Question:**_Does \(G\) contain a subset \(S\) of vertices, \(|S|\leq k\), such that every connected component of \(G-S\) has a size of, at most, \(p\)?_