# Expansion Lemma--Variations and Applications to Polynomial-Time Preprocessing
## 5 Recent Developments
### Weighted \(q\)-Expansion Lemma  
We introduced \(p\)-component order connectivity in Section 4.1 and explained how a kernel with \(\mathcal{O}(p^{3}k)\) vertices can be obtained. In this section, we explain how to obtain a kernel with \(\mathcal{O}(p^{2}k)\) vertices for the same problem using a weighted version of the expansion lemma. The weighted version of the expansion lemma was introduced by Kumar and Lokshtanov [56], who gave a kernel with \(2 pk\) vertices of this problem. A variant of this lemma was also proposed by Xiao [57], who also gave an \(\mathcal{O}(pk)\) kernel for this problem.  
We use a simpler version of the weighted expansion lemma from [11]. We start with some definitions.  
**Definition 8** (Weighted \(q\)-Expansion).: _Consider a bipartite graph \(G=(V=A\uplus B,E)\) with a weight function \(w:V(G)\to\{1,\ldots,W\}\) for an integer \(W\). Given a subset \(X\subseteq V(G)\), let \(w(X)=\sum\limits_{x\in X}w(x)\). For an integer \(q\geq 1\), a function \(f:B\to A\) is called a weighted \(q\)-expansion of \(A\) into \(B\) if_  
* _for every_ \(b\in B\)_,_ \(f(b)\in N(b)\) _, and_
* _for every_ \(a\in A\)_,_ \(w(f^{-1}(a))\geq q-W+1\)_._  
When \(W=1\), a weighted \(q\)-expansion corresponding to a \(q\)-expansion for \(a\in A\), \(w(f^{-1}(a))\geq q\), and \(w(f^{-1}(a))\) is the number of neighbors of \(a\) in \(B\).  
**Lemma 4** (Weighted expansion lemma [11]).: _Let \(q\) and \(W\) be positive integers. Consider a bipartite graph \(G=(V=A\uplus B,E)\) with weight function \(w:V(G)\to\{1,\ldots,W\}\) such that_  
1. \(w(B)\geq q|A|\)_; and_
2. _There are no isolated vertices in_ \(B\)_._ _Then there exist non-empty vertex sets_ \(X\subseteq A\)_,_ \(Y\subseteq B\) _and a function_ \(f:Y\to X\) _such that_
* \(f\) _is a weighted_ \(q\)_-expansion of_ \(X\) _into_ \(Y\)_, and_
* _No vertex in_ \(Y\) _has a neighbor outside_ \(X\)_, i.e.,_ \(N(Y)\subseteq X\)_._  
_Furthermore, the sets \(X\) and \(Y\) and the function \(f\) can be found in time \(\mathcal{O}(mn^{1.5}W^{2.5})\)._  
We first provide a kernel with \(\mathcal{O}(p^{2}k)\) vertices for \(p\)-component order connectivity for the problem (discussed in [11]) as a precursor to the kernel with \(2 pk\) vertices by Kumar and Lokshtanov [56]. Recall the auxiliary bipartite graph in Section 4.1 with modulator \(X\) on one side and \(\mathcal{C}\), the connected components of \(G-X\), in the other one. For each connected component in \(\mathcal{C}\), we assign its weight as the number of vertices in the component. Note that these weights are at most \(p\). For all the vertices in \(X\), we assign weight \(1\).  
We now apply Lemma 4 with \(q=2p-1\) to obtain a subset \(H\subseteq X\) and a subset \(C\subseteq\mathcal{C}\) such that there is a weighted \(q\)-expansion of \(H\) into \(\mathcal{C}\). For any optimal solution \(S\), we look at the set \(S^{\prime}=S\setminus(H\cup C)\cup H\). The weighted \(q\)-expansion gives us disjoint connected sets in the auxiliary bipartite graph, each of whose weight is at least \(q-p+1\geq p\). Thus, we can conclude that the weighted \(q\)-expansion represents a connected set of size at least \(p+1\) in \(G\), which any solution needs to hit. Similar to the argument in Section 4.1, we can prove that \(S^{\prime}\) is an optimal solution. Thus, we have a reduction rule as long as Lemma 4 is applicable. If this is not the case, we have \(w(\mathcal{C})\leq q|X|\leq(2p-1)(p+1)k\) in the auxiliary bipartite graph. From the conclusion that the number of vertices in \(G-X\) is \(w(\mathcal{C})\), we have a \(\mathcal{O}(p^{2}k)\) kernel.  
Note that in the kernel with \(\mathcal{O}(p^{3}k)\) vertices for \(p\)-component order connectivity described in Section 4.1, we were not able to capture the sizes of the components in the auxiliary bipartite graph. We manage to do so using weighted expansions.  
Kumar and Lokshtanov [56] use some further ideas and linear programming to improve the kernel size to \(2 pk\).