# Expansion Lemma--Variations and Applications to Polynomial-Time Preprocessing
## Box 30
### Balanced Expansion and Balanced Crown Decomposition
_there are no edges from_ \(C\) _to_ \(R\)_,_
2. \(w(Q)<\lambda\) _for each_ \(Q\in\mathbb{CC}(C)\)_,_
3. \(f(Q)\in N(Q)\) _for every_ \(Q\in\mathbb{C}(C)\)_,_
4. \(w(h)+w(f^{-1}(h))\geq\lambda\) _for each_ \(h\in H\)_, and_
5. \(G[R^{\prime}]\) _is connected and_ \(\lambda\leq w(R^{\prime})\leq 3\lambda-3\) _for each_ \(R^{\prime}\in\mathfrak{R}\)_._  
The first four properties are those of crown property with some added weight specifications (see [57]), and the last property ensures that all parts of the partition are fairly balanced. Moreover, the fourth condition implies that every \(u\in H\) should be connected to component(s) of \(G[C]\) with weight at least \(\lambda-1\). The notion of the \(\lambda\)-balanced crown decomposition is something that Casel et al. [60] contributed toward when obtaining new results. However, a crucial contribution of Definition 11 by [60] is the fifth condition. The fifth condition states that every part of the partition of \(R\) is of weight within the range \([\lambda,3\lambda-3]\). Lemma 7 (balanced expansion lemma) was not directly used to prove any kernel upper bound result, but was used by Casel et al. [60] to prove the \"balanced crown lemma\" that we state below. **Lemma 9** (Balanced Crown Lemma [60]). : _Let \(G=(V,E,w)\) be a vertex-weighted graph and \(\lambda\in\mathbb{N}\), such that each connected component in \(G\) has a weight of at least \(\lambda\). A \(\lambda\)-balanced crown decomposition \((C,R,\mathfrak{R},f)\) of \(G\) can be computed in \(\mathcal{O}(k^{2}|V||E|)\)-time where \(k=|H|+|\mathfrak{R}|\leq\min\{w(G)/\lambda,|V|\}\)._  
Casel et al. [60] used Lemma 9 to obtain a kernel for the weighted version of a separation and packing problem that we define below. Note that \(W\)-Weight Separator can be viewed as a weighted variant of the \(p\)-component order connectivity problem, and \(W\)-Weight Packing is simply its packing analog (see Box 31 and Box 32 below). **Box 31**. : \(W\)-Weight Separator  
**Input:**_A vertex-weighted undirected graph \(G=(V,E,w)\) and integer \(k\)._  
**Question:**_Is there a set \(S\subseteq V(G)\) of, at most, \(k\) vertices, such that every connected component of \(G-S\) has a total weight of less than \(W\)?_  
**Box 32**. : \(W\)-Weighted Packing Problem. **Input:**_A vertex-weighted undirected graph \(G=(V,E,w)\) and integers \(k\)._  
**Question:**_Are there \(k\) pairwise disjoint sets \(V_{1},\ldots,V_{k}\), such that for every \(1\leq i\leq k\), \(V_{i}\subseteq V(G),w(V_{i})\geq k\) and \(G[V_{i}]\) is connected?_  
For both these above mentioned problems, Casel et al. [60] provided kernels with \(3k(W-1)\) vertices, which can be computed in \(\mathcal{O}(k^{2}|V||E|)\)-time. Finally, they studied the balanced connected partition problem stated below. In the same paper, they use Definition 11 and Lemma 9 to give a polynomial time for Max-Min (Min-Max) Balanced Connected Partition, which outputs a partition \(V_{1}^{*},\ldots,V_{k}^{*}\) of \(V(G)\) such that for each \(i\in[k]\), \(G[V_{i}]\) is connected and \(w(V_{i}^{*})\geq W/3\) to give an approximation algorithm for Max-Min (Min-Max) Balanced Connected Partition as defined in Box 33. **Box 33. ** Balanced Connected Partition Problem. Max-Min (Min-Max) Balanced Connected Partition  
**Input**: _A vertex-weighted undirected graph \(G=(V,E,w)\) and integer \(k\)._  
**Question:** _Is there a partition \(V_{1},\ldots,V_{k}\) of \(V(G)\) such that for each \(i\in[k]\), \(w(V_{i})\geq W\) and \(G[V_{i}]\) is connected?_