# 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
In fact, if such a node exists, then there are no assignments of \(B_{1}\) and \(B_{2}\) to nodes in \(A\cap R^{\prime}\) such that all nodes in \(A\cap R^{\prime}\) belong to one of the two bicliques but no bicliques covers 3 nodes in \(A\cap R^{\prime}\) (recall that if a biclique covers 3 nodes in \(A\cap R^{\prime}\) we get a contradiction because then all nodes in \(A\cap L^{\prime}\) are covered by the same biclique and hence the fourth node in \(A\cap R^{\prime}\) is covered as well by that biclique). Also similarly, this implies that \(B_{1}\) and \(B_{2}\) both cover exactly two distinct nodes \(A\cap R^{\prime}\). Let \(r_{1},\ldots r_{4}\in A\cap R^{\prime}\). W.l.o.g., we assume that \(F(r_{1})=\{B_{1},C_{1}\}\) and \(F(r_{2})=\{B_{1},C_{2}\}\), \(F(r_{3})=\{B_{2},D_{1}\}\) and \(F(r_{4})=\{B_{2},D_{2}\}\) where by kernelization we have \(C_{1}\
eq C_{2}\) and \(D_{1}\
eq D_{2}\). Now, we have that all nodes in \(A\cap L^{\prime}\setminus\{u\}\) do not belong to both \(B_{1}\) and \(B_{2}\). For sake of contradiction, let, w.l.o.g., \(v\in A\cap L\setminus\{u\}\) be a node that belongs to \(B_{1}\). We know that \(v\) does not belong to \(B_{2}\) (by kernelization). So \(\{B_{1},D_{1},D_{2}\}\subseteq F(v)\), as it is connected to \(r_{3},r_{4}\) and hence \(F(v)>2\), giving a contradiction. This implies, for any node \(v\in A\cap L^{\prime}\setminus\{u\}\) to be connected to all nodes in \(A\cap R^{\prime}\), that the following conditions are met: \(\{C_{1},C_{2}\}=\{D_{1},D_{2}\}\) and \(F(v)=\{C_{1},C_{2}\}\). By kernelization, this gives a contradiction, as two distinct nodes in \(A\cap L^{\prime}\setminus\{u\}\) belong to the same set of bicliques. We have shown that in any \((2,k)\)-biclique cover \(\mathcal{B}\) of \(G^{\prime}\) there is at least one biclique \(A^{\prime}\) covering all nodes in \(A\). Now notice that there can be only one biclique covering all nodes in \(A\), as otherwise there will be two nodes with the same set of bicliques in the cover on the same side of the graph. Hence, \(A^{\prime}\) is the unique biclique covering all nodes in \(A\) in any \((2,k)\)-biclique cover. Finally, by applying Lemma 4 to all nodes connected to each node in \(A\cap L^{\prime}\) (resp. \(A\cap R^{\prime}\)), we know that the unique biclique \(A^{\prime}\) is \((A^{\prime}_{L},A^{\prime}_{R})\), as in the statement of the lemma. The previous lemma means that if \(A\) is a \(K_{3,4}\) (or \(K_{4,3}\)) of \(G^{\prime}\) then the biclique \(A^{\prime}\) obtained as in the statement is part of any optimal solution. Also notice that clearly if in a given \((2,k)\)-biclique cover of \(G^{\prime}\) there is a biclique of size at least 3 in the smallest side, and at least 4 in the largest side, this biclique induces a \(K_{3,4}\) (or \(K_{4,3}\)) in \(G^{\prime}\). Hence, by enumerating all \(K_{3,4}\) and \(K_{4,3}\) in \(G^{\prime}\) in polynomial time we can find a set \(\mathcal{B}^{\prime}\) of bicliques in \(G^{\prime}\) such that: \(\mathcal{B}^{\prime}\) contains all large enough bicliques--i.e., with \(\geq 3\) nodes (resp. \(\geq 4\)) in the smaller (resp. larger) side that are part of all \((2,k)\)-covers of \(G^{\prime}\); and no biclique not in \(\mathcal{B}^{\prime}\) which is large enough (again it contains a \(K_{3,4}\) or a \(K_{4,3}\)) is part of any \((2,k)\)-biclique cover. This is done in Step 2 of Algorithm 1. Step 3: Small Bicliques

We know that all the bicliques necessary to cover the remaining edges of \(G^{\prime}\) (besides the one in \(\mathcal{B}^{\prime}\)) need to involve at most 3 nodes in the smaller side. We can then enumerate a set \(\mathcal{C}^{\prime}\) of bicliques, in polynomial time, containing a super-graph of each biclique not in \(\mathcal{B}^{\prime}\) that is part of any \((2,k)\)-biclique cover. It is possible to verify that at the end of Step 3 of the algorithm, \(\mathcal{C}^{\prime}\) contains at least one biclique that covers all edges of any biclique with at most 3 nodes in the smallest side of the biclique. Step 3 runs in polynomial time.