# Scale Reduction Techniques for Computing Maximum Induced Bicliques
## 3 Exact Algorithm Based on the Proposed Scale Reduction
### Scale Reduction Techniques
#### 3.2.2 Scale Reduction for the MEB Problem  
The scale reduction used for the MEB problem is very similar to the one just described for the MB problem. Given \(G=(V,E)\), consider a biclique \(V^{\prime}\) of size \(\mathcal{L}\) in \(G\), a subset of edges \(H\subset E\) and the corresponding induced subgraph \(G[H]\). Let  
\[\bar{E}(H,\{u,v\})=\{\{i,j\}\in E:i\in N_{G[H]}(u)\setminus N_{G}(v),j\in N_{ G[H]}(v)\setminus N_{G}(u)\}\]  
be the set of edges between \(N_{G[H]}(u)\setminus N_{G}(v)\) and \(N_{G[H]}(v)\setminus N_{G}(u)\) in \(G\). We will abuse the notation to define the analog of operator \(P^{\mathcal{L}}_{G}(H,\{u,v\})\) introduced for the MB problem in (10) as follows:  
\[P^{\mathcal{L}}_{G}(H,\{u,v\})=\left\{ \begin{array}{ll}\{u,v\},&\text{if } \min\{|\bar{E}|,A\}\geq\mathcal{L},\\ \emptyset,&\text{otherwise},\end{array} \right. \tag{14}\]  
where \(\bar{E}\equiv\bar{E}(H,\{u,v\})\), \(A\equiv\alpha(G[N_{G[H]}(u)\setminus N_{G}(v)])\times\alpha(G[N_{G[H]}(v) \setminus N_{G}(u)])\). Whenever we discuss the MB problem, the definition of \(P^{\mathcal{L}}_{G}(H,\{u,v\})\) given in (10) applies, whereas for the MEB problem we will use the definition of \(P^{\mathcal{L}}_{G}(H,\{u,v\})\) from (14). This allows us to use definitions of \(P^{\mathcal{L}}_{G}(H)\) in (11) and \(P^{\mathcal{L}}(E,k)\) in (12) for the MEB problem as well. All the properties of the scale reduction process for the MB problem hold for the case of MEB as well. This includes Lemma 1, Algorithm 2, and the Inequality (13), which is now valid for every optimal solution of the MEB Formulation (7)-(9). Note that in this case the operator function keeps an edge if the minimum among \(|\bar{E}|\) and the total possible number of edges between maximum independent sets of \(G[N_{G[H]}(u)\setminus N_{G}(v)]\) and \(G[N_{G[H]}(v)\setminus N_{G}(u)]\), required to form a biclique, is at least \(\mathcal{L}\). In practice for sparse networks, it is often sufficient to count the number of edges in \(\bar{E}\), which can be done efficiently. We will only need to compute the independence numbers if \(|\bar{E}|\geq\mathcal{L}\). **Example 2**. : _Figure 2 illustrates the process for the same example as in Figure 1. We consider the same lower bound solution \(V^{\prime}=V^{\prime}_{1}\cup V^{\prime}_{2}\), where \(V^{\prime}_{1}=\{6\}\) and \(V^{\prime}_{2}=\{3,\,4,\,5,\,7,\,9\}\). This time it yields a lower bound \(\mathcal{L}=|V^{\prime}_{1}|\cdot|V^{\prime}_{2}|=5\) on the size of a MEB in \(G\). For edge \(\{1,\,7\}\), observe that \(G[N_{G}(1)\setminus N_{G}(7)]=\{7\}\), \(G[N_{G}(7)\setminus N_{G}(1)]=\{1,\,2,\,6\}\) and \(\bar{E}\equiv\bar{E}(E,\{1,\,7\})=\{\{1,\,7\},\{2,\,7\},\{6,\,7\}\}\), so \(|\bar{E}|=3<\mathcal{L}=5\). Therefore, \(P^{\mathcal{L}}_{\mathrm{G}}(E,\{1,\,7\})=\emptyset\). For edge \(\{4,\,8\}\), \(G[N_{G}(4)\setminus N_{G}(8)]=\{6,\,8\}\), \(G[N_{G}(8)\setminus N_{G}(4)]=\{1,\,4,\,7,\,9\}\) and \(\bar{E}\equiv\bar{E}(E,\{4,\,8\})=\{\{4,\,6\},\{6,\,7\},\{6,\,9\},\{1,\,8\},\{4,\,8\},\{7,\,8\},\{8,\,9\}\}\), so \(|\bar{E}|=7>\mathcal{L}=5\). Next, we need to compute the independence numbers for \(G[\{6,\,8\}]\) and \(G[\{1,\,4,\,7,\,9\}]\). We have: \(\alpha(G[\{6,\,8\}])=2\), \(\alpha(G[\{1,\,4,\,7,\,9\}])=3\). Since \(\min\{7,\,2\times 3\}=6>\mathcal{L}=5\), we obtain \(P^{\mathcal{L}}_{\mathrm{G}}(E,\{4,\,8\})=\{4,\,8\}\). After performing the recursive procedure for \(k=1\), we obtain a graph \(G[P^{\mathcal{L}}(E,1)]\) with no conflict edges (Figure 2b). Clearly, vertices 1 and 2 cannot be a part of a biclique with at least 5 edges, so they can be permanently removed, and a MEB of \(G\) must be a part of \(G[\{3,\,4,\,5,\,6,\,7,\,8,\,9\}]\)._  
_If we assume that the graph contains a biclique with 6 edges and set the lower bound to \(\mathcal{L}=6\), we obtain a graph \(G[P^{\mathcal{L}}(E,1)]\) with no conflict edges (Figure 2c). Removing the isolated vertices 1, 2, 3 and 5 from this graph we obtain a biclique ([6, 8], [4, 7, 9]) with 6 edges.