# 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
Step 4: Max Coverage

Finally, we have a set \(\mathcal{B}^{\prime}\), which contains bicliques that are necessary part of any optimal solution of \(G^{\prime}\) and a set \(\mathcal{C}^{\prime}\) of bicliques \(G^{\prime}\) that are sufficient to cover all edges of \(G^{\prime}\) not covered by bicliques in \(\mathcal{B}^{\prime}\). Let \(\mathcal{B}\) be the set of bicliques of \(G\) obtained by \(\mathcal{B}=\{\texttt{kern}(B^{\prime})|B^{\prime}\in\mathcal{B}^{\prime}\}\) (recall the definition of the mapping). Similarly we obtain the set \(\mathcal{C}\) from \(\mathcal{C}^{\prime}\). The algorithm will output all the bicliques in \(\mathcal{B}\). For \(t=|\mathcal{B}|\leq k\) the algorithm will obtain the remaining \(k^{\prime}=k-t\) bicliques in the following way. First, let \(\mathcal{O}=\mathcal{B}\). The algorithm will add greedily a single biclique from \(\mathcal{C}\) to \(\mathcal{O}\) for \(k^{\prime}\) times choosing each time the biclique that maximizes the number of newly covered edges in \(G^{\prime}\). It is easy to see that, since this function is monotone submodular and \(k^{\prime}\) additional bicliques are sufficient to cover all edges not covered by \(\mathcal{B}\), at least \((1-\frac{1}{\epsilon})|E|\) of the edges of \(G\) are covered at the end of the process. We can now complete the proof of Theorem 1. Proof of Theorem 1.: Notice that by the previous considerations, the set \(\mathcal{O}\) at the end of Algorithm 1 contains at most \(k\) bicliques, and these bicliques covers \((1-\frac{1}{\epsilon})|E|\) edges of \(G\). The algorithm requires \(O(|V|^{3})\) time for the kernelization. Then, the remaining graph \(G^{\prime}\) has at most \(n=\min(2k^{2},|V|)\) nodes and at most \(m=\min(4k^{4},k|E|)\) edges, by Lemma 3. The most expensive operation is enumerating all the \(K_{3,4}\), \(K_{4,3}\) of the graph which can be done in \(O(n^{7})\) time. Hence, Step 2 takes \(O(n^{7}m)\) time. Step 3 takes at most \(O(n^{6})\) time. Finally, Step 4 does at most \(k\) iterations over a set of size \(O(n^{6})\) each step of the iteration taking at most \(O(|E|)\) time. The total is hence \(O(|V|^{3}+kn^{7}|E|)\), and the result follows. #### 3.2.2 Covering All Edges with the Minimum Number of Bicliques

In this section we prove Theorem 2, the existence of an algorithm that outputs a set of at most \(H(9)k\) bicliques covering all edges of the graph. Theorem 2.: _There exists a \(O\left(\min\left(|V|^{3}+k^{15}|E|,k|V|^{7}|E|\right)\right)\) time algorithm that given in input a bipartite graph \(G=(L,R,E)\) and a parameter \(k\), where \(G\) is a yes-instance of the \((2,k)\)-biclique cover problem, outputs: a set of at most \(H(9)k\) bicliques in \(G\) covering all edges of \(G\)._

Here, \(H(i)=\sum_{1\leq j\leq i}j^{-1}\) is the \(i\)-th harmonic number and \(H(9)\approx 2.83\). For this problem, we use similar techniques described before. We outline the main differences from Algorithm 1. As before, we will construct the set \(\mathcal{B}^{\prime}\), which contains large bicliques that are part of any optimal solution. In this set, besides the bicliques including a \(K_{3,4}\) (or \(K_{4,3}\)), we will identify as well certain bicliques with size \(K_{2,a}\) for \(a\geq 5\) and \(K_{1,b}\) for \(b\geq 10\) (and the cases \(K_{a,2},K_{b,1}\)). This will ensure that all remaining bicliques necessary for covering all edges in \(G^{\prime}\) will have at most \(9\) edges in \(G^{\prime}\) (i.e., they will be \(K_{3,3}\), \(K_{2,a}\), \(K_{a,2}\) for \(a\leq 4\) and \(K_{1,b}\), \(K_{b,1}\) for \(b\leq 9\).) Then, we cast the problem of selecting the minimum number of bicliques in \(\mathcal{C}^{\prime}\) that cover all remaining edges of \(G^{\prime}\) (besides the one in \(\mathcal{B}^{\prime}\)) as a set cover problem with sets of size at most \(9\).