# 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
There is a \((2,k)\)-biclique cover of \(G^{\prime}\) which contains all bicliques in \(\mathcal{B}^{\prime}\) and only other bicliques with at most \(9\) edges. Proof. : The lemma follows by combining Lemmas 5 and 6. By Lemma 5, we know that there is no other biclique in any \((2,k)\)-biclique cover with at least \(3\) nodes on the smaller side and at least \(4\) on the largest side. Suppose there is a \((2,k)\)-biclique cover of \(G^{\prime}\) containing all bicliques of \(\mathcal{B}^{\prime}\) and another biclique \(B=(L_{B},R_{B})\
otin\mathcal{B}^{\prime}\) of the form \(K_{2,a}\) for \(a\geq 5\). If nodes in \(L_{B}\) are part of a \(K_{3,4}\) biclique, we get a contradiction, as we have two nodes in \(L_{B}\) that are both covered by the biclique \(B\) and the other biclique in \(\mathcal{B}^{\prime}\) identified by the algorithm (by kernelization this is not possible). So we know that \(L_{B}\) is not part of a \(K_{3,4}\) biclique. However, in this case, by construction of the algorithm, there is another biclique \(\mathcal{B}^{\prime}\) covering \(L_{B}\), so again we get a contradiction. (The same proof works for the \(K_{a,2}\) case for \(a\geq 5\)). Finally notice that, by construction, at most \(9\) edges of each node are left uncovered by bicliques in \(\mathcal{B}^{\prime}\) so there is a \((2,k)\)-biclique cover that includes all bicliques in \(\mathcal{B}^{\prime}\) and other bicliques with at most \(9\) edges each. Finally, notice that we can enumerate the set \(\mathcal{C}^{\prime}\) of all bicliques with at most \(9\) edges necessary to cover the edges left uncovered by the bicliques in \(\mathcal{B}^{\prime}\) in time \(O(n^{6})\), where \(n\) is the number of nodes in the graph \(G^{\prime}\). The proof of Theorem 4.2 follows by the properties of set cover. ### NP-Complete Result for \(f\geq 5\)

Theorem 3.1: \((f,k)\)_-biclique cover is NP-Complete for any \(f\geq 5\)._

### Proof of Theorem 3.1

Recall that the \((\Delta,k)\)-clique vertex partition problem is defined as follows. Given a graph \(G=(V,E)\), with maximum degree \(\leq\Delta\) and an integer \(k\), determine whether there is a partition of nodes in \(V\) in \(t\leq k\) subsets \(C_{1},\ldots,C_{t}\), such that each subset \(C_{i}\) is a clique. [PERSON] et al. (2019) showed a reduction to clique vertex partition from the NP-Complete Clause-Linked Planar 3-SAT problem [PERSON] et al. (2019). The latter is the following decision problem: given a CNF formula, where each clause contains either 2 or 3 literals and each literal appears in exactly 3 clauses (twice negated and once positive), determine whether the formula is satisfiable. [PERSON] et al. (2019) showed that given such formula \(\phi\) we can construct a graph \(G_{\phi}=(V_{\phi},E_{\phi})\) such that nodes in \(V_{\phi}\) can be partitioned in \(|X|+3|C|\) cliques iff \(\phi\) is satisfiable (where \(X\) and \(C\) are the sets of variables and clauses of \(\phi\), respectively). The graph \(G_{\phi}\) is constructed as follows. For each variable \(x\in X\), create the subgraph \(G_{x}=(\{x,x^{+},x_{1}^{-},x_{2}^{-}\},\{xx^{+},xx_{1}^{-},xx_{2}^{-},x_{1}^{- }x_{2}^{-}\})\). For each clause \(c\in C\), create a 7-node cycle \(G_{c}\). If the clause \(c\) has 3 literals \(x\),\(y\),\(z\), fix three non pairwise adjacent nodes: \(c(x)\), \(c(y)\), \(c(z)\) in the cycle (e.g., let \(c(x)\) be at distance two from \(c(y)\), and let \(c(y)\) be at distance two from \(c(z)\) and let \(c(z)\) be at distance three from \(c(x)\)). If the clause has two variables, ignore \(c(z)\). Now, for each literal \(x\) if \(c\) is the clause in which it appears positive, let the \(c(x)\) node in \(G_{c}\) be coincident with the node \(x^{+}\) in \(G_{x}\). For the clauses in which \(x\) appears negated, we similarly use nodes \(x_{1}^{-}\) and \(x_{2}^{-}\). The following result is a corollary of those of [PERSON] et al. (2019). Lemma 9: \((\Delta,k)\)_-clique vertex partition is NP-Complete for \(\Delta\geq 4\)._

Proof: By [PERSON] et al.