Given a minimum biclique edge cover, is it always possible to assign each biclique to a distinct left node (which it contains)?

ie one such assignment for this graph (from wikipedia): http://upload.wikimedia.org/wikipedia/commons/f/f7/Bipartite-dimension-biclique-cover.svg could be

(numbering the left vertices from 1 through 5 going down)

blue: 1

red: 2

green: 3

black: 4

  • 2
    $\begingroup$ Yes. Hint: Hall’s theorem. $\endgroup$ Nov 18 '14 at 19:15

Thanks to Tsuyoshi's comment, I have the solution.

It's always possible to take some subset of lefts (of size k) and construct a set of k bicliques covering all the edges connected to those lefts (assign each left to it's own biclique together with all its right-neighbors). This means that for any subset of k bicliques in the minimum biclique cover, there are at least k lefts contained in the union of those bicliques.

Now we can construct the bipartite graph which contains a left node for each biclique in the minimum cover and a right node for each left node in the original graph. There is an edge between a left and right if the corresponding biclique contains the corresponding right in the original graph. The lemma above translates exactly to the criteria for Hall's theorem in this new graph which means there exists a matching which saturates the left side.

This corresponds to an assignment of bicliques to lefts in the original graph.


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.