# 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 prove the following result:  
**Theorem 1**. : _There exists a \(O\left(\min\left(|V|^{3}+k^{15}|E|,k|V|^{7}|E|\right)\right)\) time algorithm that given in input a bipartite graph \(G=(L,R,E)\) and a parameter \(k\), where \(G\) is a yes-instance of the \((2,k)\)-biclique cover problem, it outputs a set of at most \(k\) bicliques in \(G\) covering at least \((1-\frac{1}{e})|E|\) edges of \(G\)._  
We first provide an overview of the main ideas on which Algorithm 1, which maximizes the number of edges covered with \(k\) bicliques, is based. The algorithm has four steps. First, we use a kernelization method to obtain a smaller graph \(G^{\prime}\) which has a \((2,k)\)-biclique cover iff \(G\) has a \((2,k)\)-biclique cover. Then, we exploit the properties of the \((2,k)\)-biclique covers for the kernelized graph \(G^{\prime}\) to identify a set \(\mathcal{B}^{\prime}\) of all large enough bicliques that are part of any cover of \(G^{\prime}\). Then, we will show how to enumerate the set \(\mathcal{C}^{\prime}\) containing all possible small bicliques of any cover of \(G^{\prime}\) not in \(\mathcal{B}^{\prime}\). We will keep a mapping from bicliques in the smaller graph \(G^{\prime}\) to bicliques in the original graph \(G\). Then, we cast the problem of selecting \(\leq k\) bicliques as a monotone submodular maximization problem hence showing that we can cover at least \((1-\frac{1}{e})|E|\) edges of the original graph \(G\) with \(k\) bicliques. We now prove formally Theorem 1, showing an algorithm that outputs a set of at most \(k\) bicliques in \(G\) covering at least \((1-\frac{1}{e})|E|\) edges of \(G\). We describe each step of Algorithm 1 in details. Step 1: Kernelization. We apply the kernelization technique introduced by [PERSON] et al. [2] for showing the parametrized complexity of biclique cover, which we now recall. Given an instance \((G,k)\) of biclique cover, the kernelization obtains an instance \((G^{\prime},k)\) where \(G^{\prime}\) is constructed by applying the following two rules to \(G\): (1) remove all nodes from \(G\) with no neighbors; (2) for each set of vertices that have the same neighborhood in \(G\), keep only one of them. We call \(G^{\prime}\) the kernelized graph of \(G\) if \(G^{\prime}\) is constructed from \(G\) by applying the two rules. [PERSON] et al. [2] show that \(G\) admits a \(k\)-biclique cover iff \(G^{\prime}\) admits a \(k\)-biclique cover. We now show that using the same kernelization, \(G\) admits a \((f_{L},f_{R},k)\)-biclique cover iff \(G^{\prime}\) admits a \((f_{L},f_{R},k)\)-biclique cover. **Lemma 2**. : \(G=(L,R,E)\) _is a yes-instance of the \((f_{L},f_{R},k)\)-biclique cover problem iff the kernelized graph \(G^{\prime}=(L^{\prime},R^{\prime},E^{\prime})\) of \(G\) is a yes-instance of the \((f_{L},f_{R},k)\)-biclique cover problem._  
Proof. : The lemma is a corollary of the results for general kernelization of biclique cover [2; 7]. Notice that nodes with no neighbors can be ignored without complications. We show that one application of the rule that removes one node \(u\) if another node \(v\) has the same neighborhood transforms yes-instances into yes-instances and no-instances to no-instance. The result will follow then by induction (over the number of application of the rule). Let \(G^{\prime}\) be the graph obtained by removing \(v\in L\) from \(G\) when there is a \(v\
eq u\in L\) s.t. \(N(u)=N(v)\) (the case with \(v\in R\) is similar and omitted). Consider a \((f_{L},f_{R},k)\)-biclique cover of \(G\). Removing a node \(v\) from \(G\) and from all the bicliques involving \(v\) gives a graph that can be covered with \(\leq k\) bicliques each covering at most \(f_{L}\) nodes on the left side and \(f_{R}\) on the right side. Consider a \((f_{L},f_{R},k)\)-biclique cover of \(G^{\prime}\). As node \(u\) has the same neighbors of \(v\), we can extend each of the (at most \(f_{L}\) bicliques) covering \(u\) to include \(v\) on the left side. This preserves the fact that they are bicliques.