# 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
(2019), we know that \(\phi\) is satisfiable iff the nodes in \(V_{\phi}\) can be partitioned in \(|X|+3|C|\) cliques. Notice that graph \(G_{\phi}\) has maximum degree \(\Delta\leq 4\). Hence, \((4,k)\)-clique vertex partition is NP-Complete as well. Now, using the reduction of [PERSON] (2007), we show that \((\Delta,k)\)-clique vertex partition can be reduced to \((\Delta+1,\Delta+1,k^{\prime})\)-biclique cover for some \(k^{\prime}\geq k\). Given a graph \(G=(V,E)\), construct a bipartite graph \(B_{G}=(L,R,E_{B})\) as follows. For each node \(v_{i}\in V\), create two nodes \(x_{i}\in L,y_{i}\in R\). Moreover, for each edge \(v_{i}v_{j}\in E\), make two nodes \(x_{ij}\in L\) and \(y_{ij}\in R\). For each \(v_{i}\in V\). we have \(x_{i}y_{i}\in E_{B}\). Also for each edge \(v_{i}v_{j}\in E\). we have the following edges in \(E_{B}\)\(x_{i}y_{j},x_{ij}y_{j},x_{i}y_{ij},x_{ij}y_{ij}\). [PERSON] (2007) showed that a graph \(G\) admits a clique vertex partition in \(k\) cliques iff the edges of \(B_{G}\) can be cover by at most \(k+|E|\) bicliques. The following lemma can also be shown. Lemma 10: _Let \(G\) be a graph with maximum degree at most \(\Delta\), and let \(B_{G}\) the corresponding bipartite graph defined before, there exists a \((\Delta+1,k+|E|)\)-biclique cover of \(B_{G}\) iff there is \(k\)-clique vertex partition of \(G\)._

Proof: Suppose there is no \(k\)-clique vertex partition of \(G\). Then, by [PERSON] (2007), we know that there is no biclique cover of the edges of \(B_{G}\) with \(k+|E|\) bicliques (irrespectively of how many bicliques a node belongs). Suppose there is a \(k\)-clique vertex partition of nodes in \(G\). Let \(C\) be any set in the partition. Then, it is possible to see that \(B_{C}=(\{x_{i}|v_{i}\in C\},\{y_{i}|v_{i}\in C\})\) is a biclique in \(B_{G}\) and that \(k\) such bicliques covers all edges of the form \(x_{i}y_{i}\). Also, as the sets in the partition are disjoint, each node in \(V(B_{G})\) belongs to at most one such biclique. Now, consider the edges of the form \(x_{i}y_{j}\in E_{B}\), for \(v_{i}v_{j}\in E\). Any such edge can be covered with the biclique \(B_{ij}=(\{x_{ij},x_{i}\},\{y_{j},y_{ij}\})\). Notice that by using \(|E|\) such bicliques we can complete the cover of all the remaining edges in \(E_{B}\) (including the edges of the form \(x_{ij}y_{ij}\)). Now, each node of the form \(x_{ij}\) (or \(y_{ij}\)) belongs to only one biclique in this cover. Nodes \(x_{i}\) belong to one biclique of the form\(B_{C}\) as well as other \(deg(v_{i})\) bicliques of the form \(B_{ij}\) such that \(v_{i}v_{j}\in E\). So we have that each node is part of at most \(\Delta+1\) bicliques because of the degree of \(G\). Theorem 3 is a corollary of the above lemma. ## 4 Model II: One-Side Stochastic Model

We recall the definition of the model. In the \((f,\bar{p},k)\)-biclique cover model, there is a constant \(f\), a vector of \(k\) probabilities \(\bar{p}=p_{1},\ldots p_{k}\), and a number of factors \(k\). The input is a graph \(G=(L,R,E)\) where each node in \(L\) is assigned to \(\leq f\) factors from \([k]\) arbitrary and each node in \(R\) is assigned independently to factor \(i\) with probability \(0<p_{i}<1\). A node \(u\in L\) and a node \(v\in R\) are connected iff they share a common factor. We show that, under certain conditions on the parameters \(f\) and \(\bar{p}\), we can recover an optimal or close to optimal \((f,k,k)\)-biclique cover of the graph. We will make the following two assumptions throughout the section. First, let \(L_{i}\subseteq L\) be the set of nodes assigned to factor \(i\) in \(L\). We will always assume that for no pair \(i\
eq j\in[k]\), \(L_{i}\subseteq L_{j}\). Notice that if \(L_{i}\subseteq L_{j}\) for \(i\
eq j\) then the biclique of factor \(i\) is completely covered by the biclique of factor \(j\) and there is a equivalent \((f,\bar{p}^{\prime},k-1)\)-biclique cover model without the factor \(i\). Let \(p_{m}=\min_{i\in[k]}(p_{i})\), \(p_{M}=\max_{i\in[k]}(p_{i})\). Second, we assume that the right side \(R\) is sufficiently large w.r.t.