# 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
Notice that in Step 3 we add nodes in \(L_{B}\) only if they maintain the property \(\mathcal{I}(L_{B}\cup v)=1\), so the property continues to hold. We now show that at the end of Step 3 there is a _unique_ biclique not in the cover determined so far that covers all nodes in \(L_{B}\) in the optimal solution. Suppose there exists a set of 2 or more distinct new bicliques that covers all the nodes in the set \(L_{B}\) obtained after the end of Step 3. Notice that by Lemma 14 there is set \(S\subseteq L\) of size \(|S|\leq f\) such that only one of the two bicliques covers all nodes in \(S\). \(S\) respects the condition of the while, so we would not have exited the loop of Step 2 giving a contradiction. Hence, at the end of Step 2, there is a unique new biclique \(B\), such that all nodes in \(L_{B}\) belong to the biclique. Hence, it follows that all left nodes of biclique \(B\) are found in Step 3, (they intersect because of biclique \(B\), and the loop greedily adds all nodes that intersect). Finally, during Step 4, it is clear that we construct a biclique \(B\) that covers all the edges covered by the biclique in the optimal solution with left side given by \(L_{B}\). So there is an optimal solution that contains the biclique \(B\) computed. Time Complexity

Notice that the outer loop can be executed only \(O(k)\) times (once for each biclique found). In Step 2, the loop is executed at most \(O(n)\) times and requires at most \(O(|L|^{f})\) calls to \(\mathcal{I}\) each of cost \(O(|E|)\) for a total of \(O(|L|^{f+1}|E|)\). Step 3 requires \(O(|L|)\) calls to \(\mathcal{I}\) for a total of \(O(L|E|)\). Finally, Step 4 costs \(O(|E|)\). The total cost is \(O(k|L|^{f+1}|E|)\). The correctness of Theorem 4 follows from the previous results. ### Approximate Biclique Cover

In this section, we show that for any constants in \(\bar{p}\) subject only to \(0<p_{i}<1\) for \(i\in[k]\) we can construct an approximate solution to the problem. **Theorem 6**. : _Let \(G=(L,R,E)\) be the graph obtained by the \((f,\bar{p},k)\)-biclique cover model, such that \(|R|\geq\Omega(\log(|L|))\). There exists a \(O((|L|+|R|)^{\alpha_{f,p_{m},p_{M}}})\) time algorithm where \(\alpha_{f,p_{m},p_{M}}\) is a constant depending only on \(f\), \(p_{m}\), \(p_{M}\) but not on the size of the graph, such that, given \(G\), \(f\), \(k\), and \(p_{m}\) the algorithm outputs 1) a set of \(k^{\prime}=O(\log(|L|+|R|)k)\) bicliques covering all edges of \(G\); and 2) a set of \(k\) bicliques covering \((1-\frac{1}{e})|E|\) edges of \(G\)._

Before entering into the details of the proof, we present the main idea of the algorithm, which is the following. There exists a constant \(c_{f,p_{m},p_{M}}\) depending on \(f\), \(p_{m}\), \(p_{M}\) such that if we sample u.a.r. a set \(S\subseteq R\) of size \(|S|=c_{f,p_{m},p_{M}}\log(|L|)\) we have that for each factor \(i\in[k]\) there is a set \(S_{i}\subseteq S\) such that \(|S_{i}|\geq c^{\prime}\log(|L|)\) for some constant \(c^{\prime}<c_{f,p_{m},p_{M}}\) and all nodes in \(S_{i}\) belong to the factor \(i\). Moreover, it is possible to show that the set of common neighbors of \(S_{i}\) in \(L\) is, w.h.p., exactly the set of nodes \(L_{i}\). Given such set \(S_{i}\), we can reconstruct the biclique \(B_{i}\) that covers all nodes with factor \(i\). Now, we can list all subsets \(S^{\prime}\subseteq S\) of size \(\leq c^{\prime}\log(|L|)\) in polynomial time and construct a single candidate biclique \(B^{\prime}\) from each subset \(S^{\prime}\). We have that \(k\) of these bicliques cover all edges of \(G\), so we can cast the problem as a maximum coverage problem and find a set of \(k\) bicliques covering \((1-\frac{1}{e})|E|\) edges or as a set cover problem and find a set of \(\log(|E|)k\) bicliques covering all edges. Algorithm

We now outline the algorithm (Algorithm 3). Suppose we are given a bipartite graph \(G=(L,R,E)\) obtained by the \((f,\bar{p},k)\)-biclique cover model.