# Efficient Approximation for Restricted Biclique Cover Problems
## 3 Model I: \((f,k)\)-Biclique Cover
### Results for the \((2,k)\)-Biclique Cover
#### 3.2.1. Maximize Edge Coverage with \(k\) Bicliques
Also \(v\) is covered by at most \(f_{L}\) bicliques, and in total we use \(k\) bicliques. The nodes on the right side are still covered by the same number of bicliques. The algorithm first applies the kernelization to obtain the bipartite graph \(G^{\prime}=(L^{\prime},R^{\prime},E^{\prime})\). This can be done in time \(O(|V|^{3})\). We define \(V^{\prime}=L^{\prime}\cup R^{\prime}\). We will store a mapping \(\text{\tt{kern}}:V^{\prime}\to 2^{V}\)that records for each node in \(v\in V^{\prime}\) the set \(\mathtt{kern}(v)\) of nodes in \(V\) that had the same neighborhood and of which \(v\) is the only node left in \(G^{\prime}\) - i.e., \(\mathtt{kern}(v)\) is an equivalence class of the nodes with the same neighborhood. Notice that for each node \(v\in V^{\prime}\), \(\mathtt{kern}(v)\) contains at least one node and that all nodes in \(G\) with non-zero degree are in a unique \(\mathtt{kern}(v)\) set. ```
Assumes \(G\) is a yes-instance for \((2,k)\)-biclique cover. -- Step 1 -- Let \(G^{\prime}=(L^{\prime},R^{\prime},E^{\prime})\) be the graph obtained applying the [PERSON] et al. [2] kernelization. Store mapping kern. Let \(V^{\prime}=L^{\prime}\cup R^{\prime}\) if\(|V^{\prime}|\geq 2k^{2}\)then report no \((2,k)\)-biclique cover exists for \(G\) and quit. endif -- Step 2 -- Let \(\mathcal{B}^{\prime}\leftarrow\emptyset\). For all \(A\subseteq V^{\prime}\) such that \(G[A]=K_{3,A}\) or \(G[A]=K_{4,3}\). ```  
**Algorithm 1**ApproxMaxCover(\(G=(L,R,E),k\))  
```
``` -- Step 3 -- Let \(\mathcal{C}^{\prime}\) be the set containing all bicliques of \(G^{\prime}\) of the form:
```

**Algorithm 2**ApproxMaxCover(\(G=(L,R,E),k\))

First, notice that given a biclique \(B^{\prime}=(B^{\prime}_{L},B^{\prime}_{R})\) of \(G^{\prime}\), we can construct a biclique \(B=(B_{L},B_{R})\) of \(G\) using the mapping kern: \(B_{L}=\bigcup_{v\in B^{\prime}_{R}}\mathtt{kern}(v)\) and \(B_{R}=\bigcup_{v\in B^{\prime}_{R}}\mathtt{kern}(v)\). It is possible to observe that \((B_{L},B_{R})\) is a biclique in \(G\) if \((B^{\prime}_{L},B^{\prime}_{R})\) is a biclique in \(G^{\prime}\). Given a biclique \(B^{\prime}\) in \(G^{\prime}\), we write \(\mathtt{kern}(B^{\prime})\) for the biclique \(B\) in \(G^{\prime}\) obtained in this way. The following properties of the kernelized graph \(G^{\prime}\) of \(G\) will be exploited in the rest of the paper. **Lemma 3**. : _Let \(G=(L,R,E)\) be a yes-instance of the \((2,k)\)-biclique cover problem and let \(G^{\prime}=(L^{\prime},R^{\prime},E^{\prime})\) be the kernelized version of the graph \(G\). Then the following statements are true:_

* \(G^{\prime}\) _admits a_ \((2,k)\)_-biclique cover._
* \(|L^{\prime}\cup R^{\prime}|\leq O(k^{2})\)* _In any_ \((2,k)\)_-biclique cover of_ \(G^{\prime}\) _there are no two nodes on the same side of the graph covered by the exact same set of bicliques._

Proof. : The first statement is a corollary of Lemma 2. Notice that all nodes on the same side of \(G^{\prime}\), by construction, have distinct neighborhoods. Hence, they cannot be covered by the same set of 2 bicliques in any \((2,k)\)-biclique cover. Finally, since each node in one side is covered by distinct subsets of at most 2 bicliques out of \(k\), there are at most \(2k^{2}=O(k^{2})\) nodes in \(G^{\prime}\). Step 2: Identifying Large Bicliques in the Cover. We call \(K_{l,r}\) biclique any biclique that has exactly \(l\) nodes in the left side of the bipartite graph and exactly \(r\) nodes in the right side. For a graph \(G\) and a set of vertices \(A\), we call \(G[A]\) the induced subgraph containing all nodes \(A\) and the edges between them. We will also use the following notation. Given a \((2,k)\)-biclique cover \(\mathcal{B}\) of the graph \(G\), where \(\mathcal{B}\) is a set of bicliques covering all the edges of \(G\), we define \(F_{\mathcal{B}}(u)\) as the set of bicliques covering the node \(u\) in the cover \(\mathcal{B}\). We have \(1\leq|F_{\mathcal{B}}(u)|\leq 2\). We will omit \(\mathcal{B}\) from \(F(\cdot)\) when it is clear which cover we are discussing.