# 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
We now make a series of important observations for the structure of the \((2,k)\)-biclique cover of the kernelized graph \(G^{\prime}\) of a \((2,k)\)-biclique cover yes-instance \(G\). Lemma 4: _Let \(G\) be a yes-instance for the \((2,k)\)-biclique cover problem and let \(G^{\prime}\) be the kernelized graph of \(G\). Suppose \(A\subseteq L^{\prime}\) (resp. \(A\subseteq R^{\prime}\)) is such that \(|A|\geq 3\). Let \(\mathcal{B}\) be a \((2,k)\)-biclique cover of \(G^{\prime}\). If there is a single biclique \(B\in\mathcal{B}\) that covers all the nodes in \(A\), then, in the cover \(\mathcal{B}\), all nodes \(S\subseteq R^{\prime}\) (\(S\subseteq L^{\prime}\)) connected to all nodes in \(A\) are covered by the same biclique \(B\)._

Proof. : Fix a solution \(\mathcal{B}\) of the \((2,k)\)-biclique cover of \(G^{\prime}\). Let \(B\) be the biclique that covers all nodes in \(A\) in the solution \(\mathcal{B}\). We prove the case for \(A\subseteq L^{\prime}\), the other case is similar. First, fix three distinct nodes \(a_{1},a_{2},a_{3}\) in \(A\). All the nodes are covered by biclique \(B\). Notice that by the third item of Lemma 3, each node in \(A\) is covered by a different set of (at most 2) bicliques in \(\mathcal{B}\). Hence, there is no other single biclique \(B^{\prime}\) that covers two nodes in \(A\) (otherwise there will be two nodes both covered by the pair \(B,B^{\prime}\) of bicliques). Now consider a node \(v\in R^{\prime}\) connected to all nodes in \(A\). If \(v\) is not part of biclique \(B\), in the biclique cover \(\mathcal{B}\), all the edges \((a_{i},v)\in E\) for \(i\in[3]\) are covered by a distinct biclique. This is a contradiction, as \(v\) is covered by at most 2 bicliques in \(\mathcal{B}\). We use the previous lemma to prove the following useful result. Lemma 5: _Let \(G^{\prime}=(L^{\prime},R^{\prime},E^{\prime})\) be the kernelized graph of a \((2,k)\)-biclique cover yes-instance \(G\). Suppose that \(A\subseteq L^{\prime}\cup R^{\prime}\) is such that \(G^{\prime}[A]\) is a \(K_{3,4}\) biclique (or a \(K_{4,3}\) biclique). Let \(A_{L}=A\cap L^{\prime}\) and \(A_{R}=A\cap R^{\prime}\). Let \(A^{\prime}_{L}=\bigcap_{v\in A_{R}}N(v)\) and let \(A^{\prime}_{R}=\bigcap_{v\in A^{\prime}_{L}}N(v)\). Then the biclique \(A^{\prime}=(A^{\prime}_{L},A^{\prime}_{R})\) is part of any \((2,k)\)-biclique cover of \(G^{\prime}\) and it is the unique biclique that covers all nodes in \(A\)._

Proof. : Suppose to get a contradiction that in a given \((2,k)\)-biclique cover \(\mathcal{B}\) of \(G^{\prime}\) there is no such unique biclique \(A^{\prime}\) covering all nodes in \(A\). From now on in this proof, when we use \(F(u)\), we refer to \(F_{\mathcal{B}}(u)\), i.e., the set of bicliques covering \(u\) in the cover \(\mathcal{B}\). W.l.o.g., we assume that \(|A_{L}|=3\) and \(|A_{R}|=4\). The proof follows similarly in the opposite case. Notice that if any set of at least 3 nodes in either side of \(A\) is covered by the same biclique \(B\in\mathcal{B}\) then, \(B\) covers all nodes in \(A\). This is because, by Lemma 4, if three nodes in side \(L^{\prime}\) in \(A\) (resp. \(R^{\prime}\)) are covered by \(B\) then all nodes in side \(R^{\prime}\) in \(A\) (resp. \(L^{\prime}\)) are covered by \(B\), and this implies that the all nodes in side \(L^{\prime}\) (resp. \(R^{\prime}\)) are covered by \(B\). Consider any node \(u\in A\). If \(|F(u)|=1\), than there is a contradiction. In fact, all neighbors of \(u\) are covered by a single biclique and hence we get that more than 3 on one side are covered by the same biclique. By the previous argument than there is a biclique covering all nodes in \(A\). So we assume for the rest of the proof that \(|F(u)|=2\) for all nodes \(u\in A\). Fix a node \(u\) in \(A\cap L^{\prime}\) and let \(B_{1},B_{2}\) be the two distinct bicliques covering the node \(u\) in \(\mathcal{B}\). All nodes in \(A\cap R^{\prime}\) are covered by either \(B_{1}\) or \(B_{2}\). We now show that there is no node \(v\in A\cap R^{\prime}\) such that \(F(v)=\{B_{1},B_{2}\}\).