Monday, July 29, 2013

Cov(G) vs Rect(G)

Let G=(A,B,E) be a bipartite graph. Cov(G) stands for its biclicque weight: the total weight of a covering of G with bicliques, where the size of a biclique is the number of its vertices. Rect(G) stands for the edge count of the smallest directed graph (V,E') with A U B being a subset of V, and where for each a in A and b in B, b is accessible from a if and only if (a,b) is in E.

The question is, what's the exact relationship between Rect(G) and Cov(G)? Clearly Rect(G) <= Cov(G) <= Rect(G)2, but we should close the gaps.

No comments:

Post a Comment