# 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
Given the previous results, we can implement a function \(I(S)\) that given a set \(S\) determines correctly, in time \(O(|E|)\), whether \(|\bigcap_{u\in S}F(u)|>0\) with probability at least

\[1-\exp(-(1/3)\epsilon^{2}p_{m}|R|).\]

#### 4.1.2 Algorithm Based on the Oracle \(I\)

In this section, we will assume that there is a function \(I(S)\) that returns \(I(S)=1\) iff \(|\bigcap_{u\in S}F(u)|>0\). We will assume that the function returns the correct answers all times. Given the previous results, since we make \(O(|L|^{c})\) calls to such function, this happens w.h.p. as long as \(|R|\geq C_{f,p_{m},p_{M}}\log(|L|)\) for such sufficiently large constant \(C_{f,p_{m},p_{M}}\) depending on \(f,p_{m},p_{M}\). The algorithm is presented in Algorithm 2. ```
Mark all edges in \(E\) as uncovered. Let \(\mathcal{B}\leftarrow\mathcal{D}\) be the set of bicliques in the cover while\(\mathcal{A}u\in L\) adjacent to an uncovered edge do -- Step 1 -- \(L_{B}\leftarrow\{u\}\). -- Step 2 -- while\(\exists S\subseteq L\setminus L_{B}\) s.t. \(1\leq|S|\leq f\), \(\mathcal{I}(S\cup L_{B})=1\) and there is no biclique in \(\mathcal{B}\) that covers all nodes in \(S\cup L_{B}\)do \(L_{B}\gets L_{B}\cup S\). endwhile -- Step 3 -- for\(\forall v\in L\)do if\(v\
otin L_{B}\) and \(\mathcal{I}(L_{B}\cup v)=1\)then \(L_{B}\gets L_{B}\cup\{u\}\). endif endfor -- Step 4 -- \(R_{B}=\bigcap_{u\in L_{B}}N(u)\) \(B\leftarrow(L_{B},R_{B})\) \(\mathcal{B}\leftarrow\mathcal{B}\cup B\)  Mark all edges in \(B\) as covered. endwhile return\(\mathcal{B}\)
```

**Algorithm 2** OptCoverOneSideRandom(\(G=(L,R,E),f,p_{m},k\))

Intuition of the Algorithm

The main idea of the algorithm is to isolate a single new biclique \(B\) at a time from the optimal cover \(\mathcal{B}\) given by the model. We do so by finding any subset \(L_{B}\subseteq L\) of left nodes such that: any node in \(S\) belong to biclique \(B\); and there is no other biclique to which all nodes in \(S\) belongs. Then we will identify all the left nodes that belong to biclique \(B\). Correctness of the Algorithm

We first show the following lemma. Lemma 14: _For any biclique \(B=(L_{B},R_{B})\) in the cover \(\mathcal{B}\) given by the model, there is a set of \(S\subseteq L\) of size at most \(f\) such that \(\bigcap_{u\in S}F(u)=B\)._

Proof: Consider a node \(u\in L_{B}\). This node can belong to at most other \(f-1\) bicliques \(B_{1},\ldots B_{c}\in\mathcal{B}\) with \(c\leq f-1\). Notice that for any biclique \(B_{i}\) there exists a node \(u_{i}\) s.t. \(B\in F(u_{i})\) and \(B_{i}\
otin F(u_{i})\) (by assumption in the model left nodes in biclique \(B\) are not a subset of biclique \(B_{i}\)). Hence the set \(S=\{u,u_{1},\ldots u_{c}\}\) (where \(u_{i}\) might not be distinct) has the property that \(\bigcap_{u\in S}F(u)=B\) and \(|S|\leq f\). We now show that Algorithm 2 is correct. Theorem 5: _The Algorithm 2 computes a biclique cover for the graph \(G\) with \(k\) bicliques._

Proof: We show this by induction on the order of the bicliques determined by the algorithm. More precisely, we will show that for any \(k^{\prime}\geq 0\), there exists an optimal cover containing all the first \(k^{\prime}\) bicliques determined by the algorithm. The base case for \(k^{\prime}=0\) is obvious (no clique has been determined). Suppose the statement holds for the first \(k^{\prime}-1\) bicliques. If the algorithm ends without adding another biclique, this concludes the proof. Otherwise, let \(B\) be the \(k^{\prime}\)-th biclique determined. Notice that for the algorithm to not stop, this means that a node \(u\in L\) had at least an edge uncovered. So we know that \(u\) must belong to another biclique in an optimal cover. We will now show that until the end of Step 3, the set \(L_{B}\) preserves the property that there is a biclique \(B\) in the optimal cover (not already found) containing all nodes in \(L_{B}\). This is clearly true at the beginning (Step 1). In Step 2, we check this property explicitly.