# Efficient Approximation for Restricted Biclique Cover Problems
###### Abstract  
Covering the edges of a bipartite graph by a minimum set of bipartite complete graphs (bicliques) is a basic graph theoretic problem, with numerous applications. In particular, it is used to characterize parsimonious models of a set of observations (each biclique corresponds to a _factor_ or _feature_ that relates the observations in the two sets of nodes connected by the biclique). The decision version of the minimum biclique cover problem is NP-Complete, and unless \(P=NP\), the cover size cannot be approximated in general within less than a sub-linear factor of the number of nodes (or edges) in the graph. In this work, we consider two natural restrictions to the problem, motivated by practical applications. In the first case, we restrict the number of bicliques a node can belong to. We show that when this number is at least 5, the problem is still NP-hard. In contrast, we show that when nodes belong to no more than two bicliques, the problem has efficient approximations. The second model we consider corresponds to observing a set of independent samples from an unknown model, governed by a possibly large number of factors. The model is defined by a bipartite graph \(G=(L,R,E)\), where each node in \(L\) is assigned to an arbitrary subset of up to a constant \(f\) factors, while the nodes in \(R\) (the independent observations) are assigned to random subsets of the set of \(k\) factors where \(k\) can grow with size of the graph. We show that this practical version of the biclique cover problem is amenable to efficient approximations.  
b 2018 1 84 10.3390/a11060084 10.  
inapproximability results [3; 4]. Moreover, unless \(\mathrm{NP}\subseteq\mathrm{BPTIME}(2^{\mathrm{poly}(\log(n))})\), there are also no polynomial time \(O\left(\frac{|V|}{2^{\log^{7/8+\epsilon}(|V|)}}\right)\) or \(O\left(\frac{\sqrt{|E|}}{2^{\log^{7/8+\epsilon}(|V|)}}\right)\) approximation algorithms [1]. These results are almost tight in terms of lower-order factors of \(|V|\) as an \(O\left(\min(\frac{|V|}{\sqrt{\log(|V|)}},|E|\frac{(\log(\log(|E|))^{2}}{\log^ {3}(|E|)})\right)\) approximation algorithm is known [1].  
Given these strong impossibility results, theoretical work has focused on developing polynomial time solutions for specific graph subclasses, such as C4-free graph [13], and domino-free graphs [14]. Another line of research developed parametrized complexity results, showing that it is possible to determine in time \(O(f(k)\mathrm{poly}(n))\) whether a bipartite graph \(G\) admits a cover with at most \(k\) bicliques [2; 7] where \(f(k)\) is an exponential function of \(k\), but it does not depend on \(n\). Other work has focused on the version of the problem where bicliques are edge-disjoint or vertex-disjoint [1; 2]. [PERSON] et al. [15] studied the size of maximum cardinality of bicliques in random bipartite graph. The related problem of clique cover in non-bipartite graphs has also received significant attention [5].  
Finally, a problem related to our work here, is the local biclique cover problem [16], where for a given (not necessarily bipartite) graph \(G\) and a parameter \(f\) we want to determine whether there exists a biclique cover of the edges of \(G\) (using an arbitrary number of bicliques) in which each node belongs to at most \(f\) bicliques. [PERSON] et al. [17] studied a generalization of clique cover with applications to community detection where nodes are limited to participate in a few cliques.  
We note that the biclique cover problem is equivalent to the binary matrix factorization problem [10], where the goal is to decompose an \(n\times m\) binary matrix \(A\) into a product of \(n\times k\) and \(k\times m\) binary matrices. The minimum \(k\) for which such a decomposition exists, known as the _Boolean rank_ of \(A\), equals the minimum biclique cover number of a bipartite graph \(G\) with adjacency matrix \(A\). Biclique cover can also be seen as a form of biclustering [18].