# Expansion Lemma--Variations and Applications to Polynomial-Time Preprocessing
## Box 30
### Balanced Expansion and Balanced Crown Decomposition  
Now, we introduce the notion of _balanced crown decomposition_, _balanced expansion_, and some related polynomial-time algorithms developed by Casel et al. [60]. **Definition 9** (Balanced Expansion). : _Let \(G=(V=A\uplus B,E,w)\) be a vertex-weighted bipartite graph, where \(w^{B}_{\max}=\max_{b\in B}w(b)\). For \(q\in\mathbb{N}_{0}\), a partition \(A_{1}\cup A_{2}\) of \(A\), and \(f:B\to A\), the tuple \((A_{1},A_{2},f,q)\) is called a balanced expansion if:_  
1. \(w(a)+w(f^{-1}(a))\geq q-w^{B}_{\max}+1\) _if_ \(a\in A_{1}\)_,_
2. \(w(a)+w(f^{-1}(a))\leq q+w^{B}_{\max}-1\) _if_ \(a\in A_{2}\)_._
3. _for all_ \(b\in B\)_,_ \(f(b)\in N(b)\)_, and_
4. \(N(f^{-1}(A_{1}))\subseteq A_{1}\)_._  
_(See Figure 3 for an illustration)._  
Based on the above definition, the weight of a vertex of \(A\) combined with the weight of its pre-image is in the range of \(q-w_{\max}^{B}+1\) and \(q+w_{\max}^{B}-1\). The function \(f\) is similar to the condition of expansion in Section 4. Using the above definition, Casel et al. [60] proved the following result. **Lemma 7** (Balanced Expansion Lemma). : _Consider a vertex-weighted bipartite graph \(G=(V=A\uplus B,E,w)\) with no isolated vertices in \(B\) and \(q\geq\max_{b\in B}w(b)=w_{\max}^{B}\). A balanced expansion \((A_{1},A_{2},f,q)\) for \(G\) can be computed in the \(\mathcal{O}(mn)\)-time. Furthermore, if \(w(A)+w(B)\geq q|A|\), then \(A_{1}\
eq\emptyset\)._  
The following is a more fine-grained version of the balanced expansion defined in [60]. **Definition 10** (Fractional Balanced Expansion). : _Let \(G=(V=A\uplus B,E,w)\) be a vertex-weighted bipartite graph, where \(w_{\max}^{B}=\max_{b\in B}w(b)\). For \(q\in\mathbb{N}_{0}\), a partition \(A_{1}\cup A_{2}\) of \(A\), and \(g:E(G)\to\mathbb{N}_{0}\), the tuple \((A_{1},A_{2},g,q)\) is called a fractional balanced expansion if:_  
1. \(w(a)+\sum_{b\in B}g(ab)\geq q\) _if_ \(a\in A_{1}\)_,_
2. \(w(a)+\sum_{b\in B}g(ab)\leq q\) _if_ \(a\in A_{2}\)_,_
3. _for all_ \(b\in B\)_,_ \(\sum_{a\in A}g(ab)\leq w(b)\)_, and_
4. \(N(B_{U}\cup B_{A_{1}})\subseteq A_{1}\)_, where_ \(B_{a}=\{b\in B\mid g(ab)>0\}\) _for_ \(a\in A\)_,_ \(B_{A^{\prime}}=\cup_{a\in A^{\prime}}B_{a}\) _for_ \(A^{\prime}\subseteq A\) _and_ \(B_{U}=\{b\in B\mid\sum_{a\in A}g(ab)<w(b)\}\)_._  
Such a tuple \((A_{1},A_{2},g,q)\) can be interpreted as a fractional balanced expansion as follows. The weights of the vertices of the \(f^{-1}\) function are distributed to edges through the \(g\) function, i.e., \(g\) can be interpreted as a fractional assignment from \(v\in B\) to \(u\in N(b)\). For the non-fractional version (in Definition 9, we aim that for all \(v\in B\), \(g(uv)=w(u)\) for a unique \(u\in A\) while \(g(u^{\prime}v)=0\) when \(u^{\prime}\in A\setminus\{u\}\). The authors [60] prove the following fractional version of Lemma 7. **Lemma 8** (Fractional Balanced Expansion Lemma). : _Let \(G=(V=A\uplus B,E,w)\) be a vertex-weighted bipartite graph, where \(w_{\max}^{B}=\max_{b\in B}w(b)\). For \(q\in\mathbb{N}_{0}\), a partition \(A_{1}\cup A_{2}\) of \(A\) and \(g:E(G)\to\mathbb{N}_{0}\), a fractional balanced expansion \((A_{1},A_{2},g,q)\) can be computed \(\mathcal{O}(mn)\)-time. Furthermore, if \(w(A)+w(B)\geq q|A|\), then \(A_{1}\
eq\emptyset\)._  
Figure 3: An illustration of a balanced expansion for \(q=3\) and with \(w(v)=1\) for every vertex \(v\). The assignment \(f\) is depicted with bold edges. The authors [60] use Lemma 7 to prove the construction of a structure called \(\lambda\)_-balanced crown decomposition_ for a fixed integer \(\lambda\) described below. **Definition 11** (\(\lambda\)-balanced crown decomposition [60]). : _A \(\lambda\)-balanced crown decomposition for a vertex-weighted graph \(G=(V,E,w)\) is a tuple \((C,H,\mathfrak{R},f)\) where \((H,C,R)\) is a partition of \(V(G)\) and \(\mathfrak{R}\) is a partition of \(R\) and \(f:\mathbb{CC}\to H\) where \(\mathbb{CC}(C)\) is the set of connected components of \(G[C]\) such that:_  
1.