Bipartite dimension Information & Bipartite dimension Links at HealthHaven.com

In the mathematical field of graph theory, the bipartite dimension of a graph G = (V, E) is the minimum number of bicliques, that is, complete bipartite subgraphs, needed to cover all edges in E. A collection of bicliques covering all edges in G is called a biclique edge cover, or sometimes biclique cover. The bipartite dimension of G is often denoted by the symbol d(G). An example for a biclique edge cover is given in the following diagrams:

Example for biclique edge cover
A bipartite graph...	...and a covering with four bicliques	the red biclique from the cover	the blue biclique from the cover
the green biclique from the cover	the black biclique from the cover

[edit] Bipartite dimension of some special graphs

The bipartite dimension of a 2n-vertex crown graph equals $σ(n)$ , where

$\sigma(n)=\min \left\{\,k \mid n \le \binom{k}{\lfloor k/2 \rfloor} \,\right\}$

is the inverse function of the central binomial coefficient (DeCaen et al. 1981). Fishburn and Hammer determine the bipartite dimension for some special graphs. For example, the path $P n$ has $d(P_n) = \lfloor n/2 \rfloor$ , the cycle $C n$ has $d(C_n)=\lceil n/2\rceil$ , and the complete graph $K n$ has $d(K_n) = \lceil\log n \rceil$ .

[edit] Computational complexity

Determining d(G) is an optimization problem. The decision problem for bipartite dimension can be phrased as:

INSTANCE: A graph

G = (V, E)

and a positive integer

k

.

QUESTION: Does G admit a biclique edge cover containing at most

k

bicliques?

This problem is NP-complete, even for bipartite graphs, as proved by Orlin. It appears as problem GT18 in Garey and Johnson's classical book on NP-completeness. This decision problem is a rather straightforward reformulation of another decision problem on families of finite sets, the set basis problem, proved to be NP-complete earlier by Stockmeyer, and appearing as problem SP7 in Garey and Johnson's book. Here, for a family $\mathcal{S}=\{S_1,\ldots,S_n\}$ of subsets of a finite set $\mathcal{U}$ , a set basis for $\mathcal{S}$ is another family of subsets $\mathcal{B} = \{B_1,\ldots,B_\ell\}$ of $\mathcal{U}$ , such that every set $S i$ can be described as the union of some basis elements from $\mathcal{B}$ . The set basis problem is now given as follows:

INSTANCE: A finite set $\mathcal{U}$ , a family $\mathcal{S}=\{S_1,\ldots,S_n\}$ of subsets of $\mathcal{U}$ , and a positive integer k.

QUESTION: Does there exist a set basis of size at most

k

for $\mathcal{S}$ ?

[edit] Estimates

Although determining the bipartite dimension is computationally hard, quite a few estimates are available. For instance, Jukna and Kulikov recently established a relation between the size of a maximum matching and the bipartite dimension (Jukna and Kulikov, 2009). More precisely, they showed that for a graph G with m edges that admits a matching of size $\scriptstyle \nu$ the following holds:

$d(G)\ge \frac{\nu^2}{m}.$

[edit] References

de Caen, Dominique; Gregory, David A.; Pullman, Norman J. (1981), "The Boolean rank of zero-one matrices", in Cadogan, Charles C., 3rd Caribbean Conference on Combinatorics and Computing, Department of Mathematics, University of the West Indies, pp. 169–173, MR 0657202 .

Fishburn, Peter C.; Hammer, Peter L. (1996), "Bipartite dimensions and bipartite degrees of graphs", Discrete Mathematics 160 (1–3): 127–148, doi:10.1016/0012-365X(95)00154-O .

Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman .

Jukna, Stasys; Kulikov, A. S. (2009), "On covering graphs with complete bipartite subgraphs", Discrete Mathematics 309: 3399–3403 .

Monson, Sylvia D.; Pullman, Norman J.; Rees, Rolf (1995), "A survey of clique and biclique coverings and factorizations of (0,1)-matrices", Bulletin of the ICA 14: 17–86, MR 1330781 .

Orlin, James (1977), "Contentment in graph theory: covering graphs with cliques", Indagationes Mathematicae 80 (5): 406–424, doi:10.1016/1385-7258(77)90055-5 .

Stockmeyer, Larry J. (1975), The set basis problem is NP-complete, Technical Report RC-5431, IBM .

[edit] See also

List of NP-complete problems

[edit] External links

blog entry about bipartite dimension by David Eppstein