# 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
For this problem, it is known that the greedy algorithm gives a \(H(9)\) approximation factor showing that all remaining edges in \(G^{\prime}\) are covered with additional \(\leq H(9)(k-k^{\prime})\) bicliques plus the \(k^{\prime}\leq k\) in \(\mathcal{B}^{\prime}\) for a total of \(\leq H(9)k\) bicliques. Finally, from the biclique cover of \(G^{\prime}\), we can reconstruct the biclique cover in \(G\) with the same techniques of the previous section, outputting a cover with at most \(H(9)k\) bicliques. We show some additional properties of the kernelized graph of a \((2,k)\)-biclique cover yes-instance that will be exploited by the algorithm. In this subsection, we always assume \(G^{\prime}\) is the kernelized graph of \((2,k)\)-biclique cover yes-instance \(G\). Lemma 6: _Let \((L_{A},R_{A})\) be a \(K_{2,5}\) biclique in \(G^{\prime}\) such that \(L_{A}\) is not included in any \(K_{3,4}\) biclique in \(G^{\prime}\). Then, in any \((2,k)\)-biclique cover \(\mathcal{B}\), there is always a unique biclique that covers all the nodes in \(L_{A}\) and no other node in the left side. (A similar result holds for \(K_{5,2}\) bicliques. )_

Proof. : We first show that in any \(K_{2,5}\) biclique \((L_{A},R_{A})\), all nodes in the small side \(L_{A}\) need to belong to the same biclique in any \((2,k)\)-biclique cover. Fix a \((2,k)\)-biclique cover \(\mathcal{B}\). \(F(u)\) refers to the set of bicliques covering \(u\) in the cover \(\mathcal{B}\). Let \(L_{A}=\{u,v\}\). Suppose to get a contradiction that \(F(u)\cap F(v)=\emptyset\), then each node in \(R_{A}\) contains one biclique from \(F(u)\) and one from \(F(v)\). It is possible to verify that at most \(2\times 2=4\) distinct sets of size at most \(2\) can be formed by taking one element from \(F(u)\) and one from \(F(v)\). Hence, there are two nodes in \(R_{A}\) that are covered by the same set of bicliques, giving a contradiction as the graph is kernelized. So we know that there is a biclique \(A\in F(u)\cap F(v)\). Consider a node \(x\in R_{A}\) such that \(A\
otin F(x)\). It is easy to see that there can be only one such node, as this node must be covered by the other biclique of \(F(u)\) and the other biclique of \(F(v)\) not equal to \(A\). Again, for the kernelization, only one such node can exist. So at least \(4\) nodes in \(R_{A}\) belong to a unique biclique. Finally, notice that if there is another node in the side of \(L_{A}\) in the same biclique, that would form a \(K_{3,4}\) biclique. Let \((L_{A},R_{A})\) be a \(K_{1,10}\) biclique in \(G^{\prime}\) such that \(R_{A}\) is not in any \(K_{2,5}\) biclique including the node in \(L_{A}\) in the left part of the biclique. Then, in any optimal solution, there is a single biclique that covers the node in \(L_{A}\) and no other node on that side. Proof. : Fix a \((2,k)\)-biclique cover \(\mathcal{B}\). \(F(u)\) refers to the set of bicliques covering \(u\) in the cover \(\mathcal{B}\). Let \(u\in L_{A}\). If \(F(u)=A\), then all node in \(R_{A}\) belong to \(A\) and we can apply Lemma 4. Let \(F(u)=\{A,B\}\), we have that all nodes in \(R_{A}\) belong either to \(A\) or to \(B\) or both. W.l.o.g., let \(A\) be the more common of the two. We have that \(A\) appears at least \(5\) times. So, if any other node in \(u\) side belongs to \(A\), that would form a \(K_{2,5}\) biclique. Algorithm

We now state how the algorithm for this problem constructs the set \(\mathcal{B}^{\prime}\). First, we add to \(\mathcal{B}^{\prime}\) all bicliques including a \(K_{3,A}\), as done in Step 2 of Algorithm 1. Then, we add to \(\mathcal{B}^{\prime}\) all bicliques of the form \((\{u,v\},N(u)\cap N(v))\) (and similar form \((N(u)\cap N(v)),\{u,v\}\)) for \(u\
eq v\in L^{\prime}\) such that \(u,v\) are part of a \(K_{2,5}\) and not of a \(K_{3,A}\). Finally, we add bicliques \((\{u\},N(u))\) (and the form \((N(u),\{u\})\)) such that \(u\in L^{\prime}\) has at least \(10\) edges not covered by the bicliques added before. We claim the following property for \(\mathcal{B}^{\prime}\).