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

CC BY-SA 3.0
2017-03-21T22:15:56.827Z
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?
daniello
CC BY-SA 3.0
2017-03-22T12:42:10.577Z
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.
tammo
CC BY-SA 3.0
2017-03-24T21:36:18.843Z
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?
Neal Young
CC BY-SA 3.0
2017-03-28T09:12:38.740Z
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.
tammo
<graph-theory>
Number of solutions to the biclique cover problem
tammo
# Number of solutions to the biclique cover problem

(Asked by: username_0 on 2017-03-21)

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

**Tags:** graph-theory

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_2**: Echoing username_1'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?  
> **username_0**: 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.  

---

## 0 answers

