# 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
\[|\bigcap_{u\in S}N(u)|>(1+\epsilon)2(1-(1-p_{M})^{2f}-2 fp_{M}(1-p_{M})^{2f-1} ))|R|\]3 \[|\bigcap_{u\in S}N(u)|>(1+\epsilon)2(1-(1-p_{M})^{2f}-2 fp_{M}(1-p_{M})^{2f-1} ))|R|\]4 \[|\bigcap_{u\in S}N(u)|>(1+\epsilon)2(1-(1-p_{M})^{2f}-2 fp_{M}(1-p_{M})^{2f-1} ))|R|\]5 \[|\bigcap_{u\in S}N(u)|>(1+\epsilon)2(1-(1-p_{M})^{2f}-2 fp_{M}(1-p_{M})^{2f-1} ))|R|\]6 \[|\bigcap_{u\in S}N(u)|>(1+\epsilon)2(1-(1-p_{M})^{2f}-2 fp_{M}(1-p_{M})^{2f-1} ))|R|\]7 \[|\bigcap_{u\in S}N(u)|>(1+\epsilon)2(1-(1-p_{M})^{2f}-2 fp_{M}(1-p_{M})^{2f-1} ))|R|\]8

By union bound on the \(n\) nodes in \(L\), the result follows. Now, we fix a constant \(\tilde{c}\) such that \(\frac{1}{2}cp_{m}\geq\log_{(1-(1-p_{M})^{f})^{-1}}(3)\) and such that the requirement of Lemma 15 is satisfied. It is easy to see that for all \(i\in k\) the bicliques in the optimal cover there is a set \(S^{\prime}_{i}\subset S\) that by Lemma 16 w.h.p. is such that for \(L^{\prime}_{i}=\bigcap\
olimits_{v\in S^{\prime}_{i}}N(v)\), \(S^{\prime\prime}_{i}=\bigcap\
olimits_{v\in L^{\prime}_{i}}N(v)\), the biclique \((L^{\prime}_{i},S^{\prime\prime}_{i})\) covers more edges than the \(i\)-th biclique in the cover defining the model, w.h.p. Notice that we can obtain all subsets \(S^{\prime}\subseteq S\) in polynomial time \(O(2^{\epsilon\log(|L|)})=O(|L|^{\epsilon})\). The correctness of Algorithm 3 follows from the fact that the set \(\mathcal{C}\) contains w.h.p. each biclique from the cover defining the model, and the set \(\mathcal{C}\) has size \(O(|L|+|E|)^{\alpha_{f,p_{m},p_{M}}}\) for some constant \(\alpha_{f,p_{m},p_{M}}\) depending on \(f\), \(p_{m},p_{M}\) but not on the size of the graph or the number of bicliques. ## 5 Conclusions

We have studied two natural restrictions to the well-known problem of biclique cover in bipartite graphs that are motivated by practical applications in computational biology and other fields. For these restrictions, we have shown some non-trivial optimal or approximation algorithms which run in polynomial time. As a future work, it would be interesting to determine whether \((f,k)\)-biclique cover is NP-Complete for \(2\leq f\leq 4\) and to determine inapproximability results for general values of \(f\). A.E. and E.U. contributed equally to the paper. We thank [PERSON] for introducing us to this problem, and [PERSON] and [PERSON] for many insightful discussions on the problem. The research was partially supported by NSF grant IIS-1247581 and NIH grant R01-CA180776. The authors declare no conflicts of interest. ## References

* (1) [PERSON]; [PERSON]; [PERSON]; [PERSON] Nearly Tight Approximability Results for Minimum Biclique Cover and Partition. In _Algorithms-ESA 2014_; Springer: Berlin, Germany, 2014; pp. 235-246. * (2) [PERSON]; [PERSON] [PERSON]; [PERSON]; [PERSON] Covering graphs with few complete bipartite subgraphs. _Theor. Comput. Sci._**2009**, _410_, 2045-2053. [CrossRef]
* (3) [PERSON] On approximate solutions for combinatorial optimization problems. _SIAM J. Discret. Math._**1990**, \(3\), 294-310. [CrossRef]
* (4) [PERSON]; [PERSON] Inapproximability of nondeterministic state and transition complexity assuming \(\mathrm{P}\
eq\mathrm{NP}\). In _Developments in Language Theory_; Springer: Berlin, Germany, 2007; pp. 205-216. * (5) [PERSON] Contentment in graph theory: Covering graphs with cliques. In _Indagationes Mathematicae (Proceedings)_; Elsevier: NewYork, NY, USA, 1977; Volume 80, pp. 406-424. * (6) [PERSON]; [PERSON] On covering graphs by complete bipartite subgraphs. _Discret. Math._**2009**, _309_, 3399-3403. [CrossRef]* (7) [PERSON]; [PERSON]; [PERSON] [PERSON]; [PERSON] [PERSON]; [PERSON]; [PERSON]; [PERSON] Mod/Resc parsimony inference: Theory and application. _Inf. Comput._**2012**, _213_, 23-32. [CrossRef]
* (8) [PERSON]; [PERSON] [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] On the genetic architecture of cytoplasmic incompatibility: Inference from phenotypic data. _Am. Nat._**2013**, _182_, E15-E24.