1
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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? $\endgroup$
    – daniello
    Mar 21 '17 at 22:15
  • $\begingroup$ 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. $\endgroup$
    – tammo
    Mar 22 '17 at 12:42
  • $\begingroup$ 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? $\endgroup$
    – Neal Young
    Mar 24 '17 at 21:36
  • $\begingroup$ 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. $\endgroup$
    – tammo
    Mar 28 '17 at 9:12
1
$\begingroup$

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$ [1]. There is no polynomial-delay enumeration algorithm for all bicliques in reverse lexicographical order unless P=NP [2].

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$ [3].

[1] Vania M.F. Dias, Celina M.H. de Figueiredo, and Jayme L. Szwarcfiter. “Generating Bicliques of a Graph in Lexicographic Order”. In: Theoretical Computer Science 337.1-3 (June 2005), pp. 240–248. doi: 10.1016/j.tcs.2005.01.014.

[2] Wasa, Kunihiro. "Enumeration of enumeration algorithms." arXiv preprint arXiv:1605.05102 (2016).

[3] Alain Gely, Lhouari Nourine, and Bachir Sadi. “Enumeration aspects of maximal cliques and bicliques”. In: Discrete Applied Mathematics 157.7 (Apr. 2009), pp. 1447–1459. doi: 10.1016/j.dam.2008.10. 010.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.