# 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
the left side. In particular we assume \(|R|>C_{f,p_{m},p_{M}}\log(|L|)\) for a sufficiently large constant \(C_{f,p_{m},p_{M}}\) which depends on \(f\), \(p_{m}\), \(p_{M}\) only. This is to allow extracting enough information from the random assignment in the right part. In the rest of the section, we present two results. First, we show that under an additional condition on the constants \(\bar{p}\) that ensures that no factor has much higher probability than another factor and that no factor has too large a probability, then an exact \((f,\bar{p},k)\)-biclique cover can be obtained in polynomial time. We then show that for any vector of constants \(\bar{p}\), it is possible to obtain an approximate cover. ### Optimal \((f,\bar{p},k)\)-Biclique Cover

We first state the additional condition on \(\bar{p}\):

\[\frac{p_{m}}{2}>1-(1-p_{M})^{2f-1}(1+(2f-1)p_{M}) \tag{1}\]

Notice that for any \(f\) there is a non-empty set of vectors \(\bar{p}\) for which the condition holds. For instance, it holds for any vector s.t. \(0<p_{m}=p_{M}<c_{f}\) where \(c_{f}<1\) is constant depending on \(f\). We will prove the following theorem. Theorem 4: _Let \(G=(L,R,E)\) be the graph obtained by the \((f,\bar{p},k)\)-biclique cover model, such that \(|R|\geq\Omega(\log(|L|))\) and where the condition in Equation (1) holds for \(\bar{p}\). There exists a \(O(k|L|^{f+1}|E|)\) time algorithm that given \(G\), \(f\), \(k\) and \(p_{m}\) outputs a \((f,k,k)\)-biclique cover of \(G\) w.h.p. In the paper, we say that an event happens with high probability if it happens with probability \(\geq 1-|V|^{c}\) for some constant \(c>0\)._

Before entering into the details of the proof here we present the main ideas of the proof. First, we show that, under the condition in Equation (1) and for \(|R|\geq\Omega(\log(|L|))\), it is possible to distinguish in polynomial time w.h.p., whether in any given set \(S\subseteq L\) there exists at least a factor \(i\in[k]\), such that all nodes in \(S\) belong to the \(L_{i}\) (are assigned to the factor). In particular, we show that this is possible by just looking at the number of the common neighbors of all the nodes in \(S\). We will then assume to have an oracle \(\mathcal{I}:2^{L}\rightarrow\{0,1\}\) that returns, w.h.p. \(\mathcal{I}(S)=1\), iff there is factor to which all nodes in \(S\) belong. We will show that there is an algorithm that makes a polynomial numbers of calls to this oracle and finds an \((f,k,k)\)-biclique cover of \(G\). We stress that this algorithm could be used also for other probabilistic models where the function \(\mathcal{I}\) can be _computed_ with sufficient accuracy. The intuition of the algorithm is that we can construct each biclique in the cover, one at a time, once we identify a set of nodes \(S\subseteq L\) such that there exists a _unique_ factor \(i\in[k]\) to which all nodes in \(S\) belong. Furthermore, we show that for any factor there is at least one set of size \(\leq f\) of nodes in \(L\) for which this happens. We can then identify each biclique in polynomial time, w.h.p. We now proceed to prove formally the results the this model. #### 4.1.1 Determining Whether Nodes in \(S\subseteq L\) Share a Common factor

Recall that in this section we assume we are given a bipartite graph \(G=(L,R,E)\) obtained by the \((f,\tilde{p},k)\)-biclique cover where the condition Equation (1) holds, \(|R|\geq\Omega(\log(|L|))\) and no \(L_{i}\) set is subset of \(L_{j}\) for two distinct factors \(i,j\in[k]\). First, we show that, given a set \(S\subseteq L\), it is possible to distinguish based on the graph \(G\) whether there is at least a common factor assigned to all nodes in \(S\). In this section, we use \(F(u)\) to indicate the set of bicliques covering node \(u\) in the model (i.e., each biclique corresponds to the nodes with one factor). **Lemma 11**.