# 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
: _Given a set \(S\subseteq L\), if \(\bigcap_{u\in S}F(u)=\emptyset\) then the probability that_

\[|\bigcap_{u\in S}N(u)|>(1+\epsilon)2(1-(1-p_{M})^{2f}-2 fp_{M}(1-p_{M})^{2f-1} ))|R|\]

_for \(0<\epsilon<1\) is smaller than \(\exp\left(-1/3e^{2}C|R|\right)\), for some constant \(C\) not dependent on \(|R|\)._

Proof. : Let \(X_{w}\) be the indicator variable of the event that \(\forall u\in S\left(u,w\right)\in E\). We claim that the probability of \(X_{w}\) is upper-bounded by twice the probability of the following event: \(w\) is part of at least two bicliques selected from a set \(F^{\prime}\) of cardinality at most \(2f\). Suppose in fact that \(w\) is part of a single biclique \(B\), then as \(\bigcap_{u\in S}F(u)=\emptyset\), \(w\) cannot be connected to all nodes in \(S\). \(w\) must be part of at least two bicliques. Now, fix a single node \(u\in S\). \(|F(u)|\leq f\), and \(w\) is part of at least one biclique in \(F(u)\). If \(w\) is part of two bicliques in \(F(u)\), then our bound holds (use \(F^{\prime}=F(u)\) as a the sets from which the bicliques must be selected). If \(w\) is part of a single biclique \(B\in F(u)\), then fix \(v\in S\), a node such that \(B\
otin F(v)\) (the node exists for the empty intersection in \(S\)). We have that \(w\) is part of another biclique from \(F(v)\) with \(|F(v)|\leq f\). In this case, \(w\) is part of at least two bicliques from the set \(F^{\prime}=F(v)\cup F(u)\) of size at most \(2f\). By union bound on these two cases

\[\Pr\left(X_{w}\right)\leq 2(1-(1-p_{M})^{2f}-2 fp_{M}(1-p_{M})^{2f-1}))\]

where the inequality comes from the fact that the probability is maximized when the set \(F^{\prime}\) contains exactly \(2f\) bicliques of maximum probability \(p_{M}\), the probability of selecting at least \(2\) bicliques is the opposite of the probability of not selecting \(0\) of \(1\) biclique. Let \(X\) be the random variable that measures the cardinality of \(|\bigcap_{u\in S}N(u)|\). Then, it is easy to see that

\[\mathbf{E}\left[X\right]\leq|R|2(1-(1-p_{M})^{2f}-2 fp_{M}(1-p_{M})^{2f-1}),\]

and by the Chernoff bound, for \(0<\epsilon<1\), we have

\[\Pr\left(X>(1+\epsilon)\mathbf{E}\left[X\right]\right)<\exp\left(-1/3e^{2}2(1- (1-p_{M})^{2f}-2 fp_{M}(1-p_{M})^{2f-1}|R|)\right).\]

Similarly, we can show

**Lemma 12**. : _Let \(S\subseteq L\) such that \(\bigcap_{u\in S}F(u)\
eq\emptyset\) then the probability that \(|\bigcap_{u\in S}N(u)|<(1-\epsilon)p_{m}|R|\) for \(0<\epsilon<1\) is smaller than \(\exp\left(-1/3\epsilon^{2}p_{m}|R|\right)\)._

Proof. : Let \(X_{w}\) be the indicator variable of the event that \(\forall u\in S\), we have \((u,w)\in E\). Let \(A\) be one of the common biclique of the nodes. We have

\[\Pr\left(X_{w}\right)\geq\Pr\left(A\in F(w)\right)=p_{A}\geq p_{m},\]

the result follows by the Chernoff bound. **Lemma 13**. : _Let \(p_{m}>2(1-(1-p_{M})^{2f}-2 fp_{M}(1-p_{M})^{2f-1})\), given a set \(S\subseteq L\), then there is a constant \(0<\epsilon<1\) and a constant \(c>0\) such that, for \(|R|\in\Theta(\log(|L|))\) with probability \(\geq 1-\exp(-c|R|)\)_

\[|\bigcap_{u\in S}F(u)|>0\]

_if and only if \(|\bigcap_{u\in S}N(u)|\geq(1-\epsilon)p_{m}|R|\)._

Proof. : If \(p_{m}>2(1-(1-p_{M})^{2f}-2 fp_{M}(1-p_{M})^{2f-1}\) then there is an \(\epsilon>0\) for which \((1-\epsilon)p_{m}>(1+\epsilon)2(1-(1-p_{M})^{2f}-2 fp_{M}(1-p_{M})^{2f-1}\). Notice that \((1/3)\epsilon^{2}p_{m}>1/3\epsilon^{2}2(1-(1-p_{M})^{2f}-2 fp_{M}(1-p_{M})^{2f-1}\). Then we can apply the previous lemma and show that that with probability at least

\[1-\exp(-(1/3)\epsilon^{2}p_{m}|R|)\]

we have \(|\bigcap_{u\in S}N(u)|\geq(1-\epsilon)p_{m}|R|\) iff \(|\bigcap_{u\in S}F(u)|>0\).