# Number of solutions to the biclique cover problem

Given a bipartite graph and the number bicliques K, how many ways exist to solve the biclique cover problem using K (possibly empty) bicliques?

• What are you looking for, an algorithm that counts the number of biclique covers, or an upper/lower bound in terms of n and K? Are there any constraints that the cover should be minimal in some way? Mar 21 '17 at 22:15
• Ideally I am looking for a closed form solution (My hunch is that it must exist). There are no constraints on the cover being minimal. Mar 22 '17 at 12:42
• Echoing daniello's comment: Your answer "closed form solution" suggests that you are asking for an expression that counts the number of biclique covers with $K$ cliques. But this makes sense only if you have a particular bipartite graph in mind. Can you rephrase your question to clarify what you are asking? Mar 24 '17 at 21:36
• I am thinking about some parametrisation of all possible graphs. Essentially the number of vertices and some measure of heterogeneity of the vertex distribution should suffice. Mar 28 '17 at 9:12

Given a Graph $G=(V, E),$ it takes $O(|V|^3)$ delay and $O(2^|V|)$space to find all bicliques in lexicographical order in $G$ . There is no polynomial-delay enumeration algorithm for all bicliques in reverse lexicographical order unless P=NP .
Given a bipartite graph $G=(U, V, E),$ it takes $O((|U|+|V|)^2)$ delay with exponential space to find all maximal bicliques in $G$ in lexicographical order in $U$ .