0xDE ([info]11011110) wrote,
@ 2008-03-31 23:06:00
Previous Entry  Add to memories!  Tell a Friend  Next Entry
Entry tags:combinatorics

Biclique covers
First question: suppose you want to cover all the edges of an n-vertex complete graph with complete bipartite subgraphs (bicliques). How many bicliques do you need?

Easy, right? You can do it with ceiling(log2n) bicliques, by assigning distinct binary numbers to the n vertices and making a biclique for each bit position of these numbers, where the vertices having a 0 in the given position go on one side of the biclique and the vertices having a 1 in that position go on the other side. And conversely, if you have a biclique cover, you might as well include each vertex in each biclique, and you can assign binary labels to the vertices according to which side of each biclique they belong to, so every solution must have this form. In terms of adjacency matrices, it looks something like this:

\left(\begin{array}{cccccccc}0&1&1&1&1&1&1&1\\1&0&1&1&1&1&1&1\\1&1&0&1&1&1&1&1\\1&1&1&0&1&1&1&1\\1&1&1&1&0&1&1&1\\1&1&1&1&1&0&1&1\\1&1&1&1&1&1&0&1\\1&1&1&1&1&1&1&0\end{array}\right) =\left(\begin{array}{cccccccc}0&0&0&0&1&1&1&1\\0&0&0&0&1&1&1&1\\0&0&0&0&1&1&1&1\\0&0&0&0&1&1&1&1\\1&1&1&1&0&0&0&0\\1&1&1&1&0&0&0&0\\1&1&1&1&0&0&0&0\\1&1&1&1&0&0&0&0\end{array}\right) \vee\left(\begin{array}{cccccccc}0&0&1&1&0&0&1&1\\0&0&1&1&0&0&1&1\\1&1&0&0&1&1&0&0\\1&1&0&0&1&1&0&0\\0&0&1&1&0&0&1&1\\0&0&1&1&0&0&1&1\\1&1&0&0&1&1&0&0\\1&1&0&0&1&1&0&0\end{array}\right) \vee\left(\begin{array}{cccccccc}0&1&0&1&0&1&0&1\\1&0&1&0&1&0&1&0\\0&1&0&1&0&1&0&1\\1&0&1&0&1&0&1&0\\0&1&0&1&0&1&0&1\\1&0&1&0&1&0&1&0\\0&1&0&1&0&1&0&1\\1&0&1&0&1&0&1&0\end{array}\right)


Ok, now time for the second question. Instead of covering a complete graph, let's cover a different graph Gn, in the form of a bipartite graph Kn,n minus a perfect matching. Since Gn is bipartite, we might as well describe it with a simplified adjacency matrix in which one side of the bipartition indexes the rows and the other side indexes the columns. But this simplified adjacency matrix for Gn is identical to the adjacency matrix of the clique Kn that we started with, zero on the main diagonal and all ones elsewhere! We're just interpreting it differently. In this interpretation, the bicliques we're covering G with can only cover half as many of the ones in the adjacency matrix as they could when we were covering a complete graph. So we need twice as many bicliques, right?

Wrong!

Here's an example, expressed in terms of adjacency matrices, of a biclique cover of G6.

\left(\begin{array}{cccccc}0&1&1&1&1&1\\1&0&1&1&1&1\\1&1&0&1&1&1\\1&1&1&0&1&1\\1&1&1&1&0&1\\1&1&1&1&1&0\end{array}\right)= \left(\begin{array}{cccccc}0&0&0&1&1&1\\0&0&0&1&1&1\\0&0&0&1&1&1\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}\right)\vee\left(\begin{array}{cccccc}0&1&1&1&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&1&1&1&0&0\\0&1&1&1&0&0\end{array}\right)\vee\left(\begin{array}{cccccc}0&0&0&0&0&0\\0&0&0&0&0&0\\1&1&0&0&0&1\\1&1&0&0&0&1\\1&1&0&0&0&1\\0&0&0&0&0&0\end{array}\right)\vee\left(\begin{array}{cccccc}0&0&0&0&0&0\\1&0&1&0&1&0\\0&0&0&0&0&0\\1&0&1&0&1&0\\0&0&0&0&0&0\\1&0&1&0&1&0\end{array}\right)


This turns out to be the biggest graph Gn that can be covered by only four bicliques. It may not be obvious from the matrices above, but there's a simple way of describing this cover: let the rows and columns of the matrix both be indexed by the edges of a complete graph K4, and make a biclique for each vertex v of the K4, having on one side the edges incident to v and on the other side the edges not incident to v. Each 1 in the matrix corresponds to an ordered pair of unequal edges of the K4, and for each such pair there is a vertex that is an endpoint of the first edge of the pair and not an endpoint of the second edge, so all 1's are covered.

The construction generalizes: index the rows and columns of an adjacency matrix for Gn by the subsets of k/2 out of k items, and form a biclique for each item that has on one side the subsets not containing that item and on the other side the subsets containing that item. In this way, we can cover Gn by k bicliques whenever

n\le{k\choose\lfloor k/2\rfloor}.


This turns out to be optimal. For any cover of Gn by a family of k bicliques, and for each of the n columns of the adjacency matrix, there must be a minimal subfamily of the bicliques that covers all but that column. These minimal subfamilies form an antichain in the powerset of the bicliques, so by Sperner's theorem

n\le{k\choose\lfloor k/2\rfloor}.


Asymptotically, k = log2n(1+o(1)), the same leading term as for covering a clique by bicliques.

(8 comments) - (Post a new comment)


[info]kirpich_spb
2008-04-01 03:42 pm UTC (link)
This is interesting! Are you an author of this result?

Actually, Stasys Jukna proved that any bipartite graph whose complement has maximum degree d can be covered by c*d*ln(n) bicliques.

(Reply to this) (Thread)

[info]11011110
2008-04-01 04:30 pm UTC (link)
Thanks! I'm the author of this post. I haven't done the literature search to find who might have written on something similar before, though — thanks for the Jukna reference. Nor have I written anything more formal than this post about this, yet.

I found this while trying to reconstruct Larry Stockmeyer's reduction from vertex cover to set basis (equivalently biclique cover of bipartite graphs), which is cited in Garey and Johnson as a 1975 tech report. Based on the ideas in this post, you can translate vertex cover to biclique cover by replacing each edge by a copy of G7. The optimal biclique cover of the resulting graph has 4m+k bicliques, where m is the number of edges in the original graph and k is the size of its optimal vertex cover.

(Reply to this) (Parent)

[info]11011110
2008-04-02 01:07 am UTC (link)
So, I found On Graph Complexity by Jukna [Combinatorics, Probability and Computing 2006], which appears to use exactly the construction I described here to cover Gn by bicliques (just above the remark in the middle of page 866). Except that he doesn't analyze it carefully and sets k = 2 log2n instead of the roughly half-as-small value that would suffice.

(Reply to this) (Parent)(Thread)

[info]kirpich_spb
2008-04-03 09:50 am UTC (link)
Yes, indeed. We also proved with Stasys a few simple lower bounds for the clique covering number.

As for me, I came up to this problem when I was trying to prove lower bounds for the formula size of some functions.

(Reply to this) (Parent)
Biclique covers -- Bollobas systems
(Anonymous)
2008-04-01 07:28 pm UTC (link)
That's an interesting post, David. BTW, I believe complete bipartite graphs with a perfect matching removed, are also called Bollobas systems.

aravind srinivasan

(Reply to this) (Thread)
Re: Biclique covers -- Bollobas systems
[info]11011110
2008-04-02 02:52 am UTC (link)
Thanks. I tried looking up that phrase, but didn't find anything.

(Reply to this) (Parent)(Thread)
Re: Biclique covers -- Bollobas systems
(Anonymous)
2008-04-02 02:45 pm UTC (link)
Hi David, I remember Laci Lovasz calling such graphs Bollobas systems back in '92 over lunch, and I think the reason perhaps is as follows. A classic result in extremal combinatorics is: suppose we have two systems of sets {S_1, S_2, ..., S_m} and {T_1, T_2, ..., T_m} with |S_i| = a and |T_i| = b for each i, and such that S_i intersects T_j iff i is NOT equal to j. Then, m <= {{a + b} choose a}. [Of course, this bound is tight, by taking a universe of size a+b, the S_i to be all subsets of size a, and T_i = complement of S_i.] Apparently Bollobas came up with a proof (the first?) when he was a teenager; Spencer's "Ten Lectures ..." has a short probabilistic proof. Note that the incidence structure between the S_i and T_j is that of a complete bip. graph minus a perfect matching, maybe this is why Laci used the phrase.

Anyone care to enlighten further?

aravind

(Reply to this) (Parent)
Survey on biclique and clique covers
(Anonymous)
2008-04-02 01:35 pm UTC (link)
Hi! Nice post and related to what I've been doing. There's an old survey about all this by combinatoricians: S. Monson, N. Pullman, and R. Rees: A survey of clique and biclique coverings and factorizations of (0,1)-matrices. Bulletin of the ICA, vol 14, pp. 17--86, 1995. You might find it interesting, though the approach is more that of a mathematician than that of a computer scientist. Unfortunately I don't think that it's online. They say that this result is proved in D. de Caen, D. Gregory, and N. Pullman, The boolean rank of zero-one matrices. Proc. Third Caribbean Conf. on Combinatorics and Computing, Barbados, pp. 169--173, 1981 (but I haven't seen that paper).

Also, the concept of a Boolean rank is related, so it might be a good keyword for the future searches.

(Reply to this)

(8 comments) - (Post a new comment)

Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…