# Scale Reduction Techniques for Computing Maximum Induced Bicliques
## 3 Exact Algorithm Based on the Proposed Scale Reduction
### Scale Reduction Techniques
#### 3.2.1 Scale Reduction for the MB Problem  
For a subset of edges \(H\subset E\), the corresponding _edge-induced subgraph_\(G[H]\) of \(G\) is given by \(G[H]=(V(H),H)\), where \(V(H)=\{i\in V:\exists j\in V\text{ such that }\{i,j\}\in H\}\). Consider \(G=(V,E)\), a biclique \(V^{\prime}\) of size \(\mathcal{L}\) in \(G\), a subset of edges \(H\subset E\) and induced subgraph \(G[H]\). Define the following operator function for \(\{u,v\}\in H\):  
\[P^{\mathcal{L}}_{G}(H,\{u,v\})=\left\{ \begin{array}{ll}\{u,v\},&\text{if } \quad\alpha(G[N_{G[H]}(u)\setminus N_{G}(v)])+\alpha(G[N_{G[H]}(v)\setminus N_ {G}(u)])\geq\mathcal{L},\\ \emptyset,&\text{otherwise.}\end{array} \right. \tag{10}\]  
The operator function determines whether two adjacent vertices \(u\) and \(v\) can be simultaneously included in a biclique with at least \(\mathcal{L}\) vertices in \(G[H]\). If \(P^{\mathcal{L}}_{G}(H,\{u,v\})=\emptyset\) we will call \(\{i,j\}\) a _conflict edge_ with respect to \(H\), since at most one of its two vertices can be included in a biclique with at least \(\mathcal{L}\) vertices in \(G[H]\). Then  
\[P^{\mathcal{L}}_{G}(H)=\bigcup_{\{u,v\}\in H}P^{\mathcal{L}}_{G}(H,\{u,v\}) \tag{11}\]  
gives a subset of edges in \(H\) that results from excluding all the conflict edges. This process can be applied recursively until there are no more conflict edges with respect to the remaining set of edges. More formally, for a given lower bound \(\mathcal{L}\) and a positive integer \(k\), denote by \(P^{\mathcal{L}}(E,k)\) the following recursively defined set:  
\[P^{\mathcal{L}}(E,k)=\left\{ \begin{array}{ll}P^{\mathcal{L}}_{G}(E),&\text{if }k= 1,\\ P^{\mathcal{L}}_{G}(P^{\mathcal{L}}(E,k-1)),&\text{if }k\geq 2.\end{array} \right. \tag{12}\]  
For \(k\geq 1\), \(P^{\mathcal{L}}(E,k)\) is a subset of edges in \(E\) that were not labeled as conflict edges during \(k\) rounds of the process. **Example 1**. : _Figure 1 illustrates this process on a 9-vertex graph \(G\) with a known biclique (obtained using Algorithm 1) \(V^{\prime}=V^{\prime}_{1}\cup V^{\prime}_{2}\), where \(V^{\prime}_{1}=\{6\}\) and \(V^{\prime}_{2}=\{3,4,5,7,9\}\) giving a lower bound \(\mathcal{L}=\left|V^{\prime}_{1}\cup V^{\prime}_{2}\right|=6\) on the size of a MB in \(G\). We find \(P^{\mathcal{L}}(E,k)\) for \(k=1\). For the edge \(\{1,8\}\), we have \(G[N_{G}(1)\setminus N_{G}(8)]=\{8\}\) and \(\alpha(G[N_{G}(1)\setminus N_{G}(8)])=1\). Likewise, \(G[N_{G}(8)\setminus N_{G}(1)]=\{1,4,9\}\) and \(\alpha(G[N_{G}(8)\setminus N_{G}(1)])=3\). As a result, \(\alpha(G[N_{G}(1)\setminus N_{G}(8)])+\alpha(G[N_{G}(8)\setminus N_{G}(1)])=4 <\mathcal{L}=6\). Therefore, \(P^{\mathcal{L}}_{G}(E,\{1,8\})=\emptyset\) and \(\{1,8\}\) is a conflict edge. On the other hand, for \(\{6,7\}\), \(G[N_{G}(7)\setminus N_{G}(6)]=\{1,6,8\}\), \(G[N_{G}(6)\setminus N_{G}(7)]=\{3,4,5,7,9\}\), and \(\alpha(G[\{1,6,8\})+\alpha(G[\{3,4,5,7,9\}])=7>\mathcal{L}=6\), so \(P^{\mathcal{L}}_{G}(E,\{6,7\})=\{6,7\}\) meaning that the edge \(\{6,7\}\) is not a conflict edge. After performing the recursive procedure for \(k=1\) and \(k=2\), we obtain a graph \(G[P^{\mathcal{L}}(E,2)]\) with no conflict edges. Clearly, vertices 1, 2 and 8 cannot be a part of a biclique with at least 6 vertices, so they can be permanently removed, and a MB of \(G\) must be a part of \(G[\{3,4,5,6,7,9\}]\). Since the latter graph is complete bipartite, its set of vertices is the maximum biclique of \(G\). This shows that our lower bound solution is, in fact, optimal for this graph._  
Next, we discuss some properties of the proposed scale reduction process. The following lemma follows directly from the definition of \(P^{\mathcal{L}}(E,k)\). **Lemma 1**. : _Let \(V^{\prime}=(V^{\prime}_{1}\cup V^{\prime}_{2},E^{\prime})\) and \(V^{*}=(V^{*}_{1}\cup V^{*}_{2},E^{*})\) be bicliques in \(G=(V,E)\) with \(|V^{\prime}|=\mathcal{L}\), \(|V^{*}|=\mathcal{L}^{*}\), such that \(\mathcal{L}\leq\mathcal{L}^{*}\). Then for any integer \(k\geq 1\) the following inclusions hold:_  
1.