Bipartite dimension

In the mathematical field of graph theory, the bipartite dimension of an 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:

Bipartite dimension of some special graphs

Fishburn and Hammer determine the bipartite dimension for some special graphs. For example, the path $P\_n$ has $d(P\_n)\; =\; lfloor\; n/2\; floor$, the cycle $C\_n$ has $d(C\_n)=lceil\; n/2\; ceil$, and the complete graph $K\_n$ has $d(K\_n)\; =\; lceillog\; n\; ceil$.

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\}$?

References

* P. C. Fishburn and P. L. Hammer. Bipartite dimensions and bipartite degrees of graphs. "Discrete Mathematics", 160:127-148, 1996
* M. R. Garey and D. S. Johnson. "". Freeman, 1979.
* 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.
* J. Orlin. Contentment in Graph Theory: Covering Graphs with Cliques. "Indagationes Mathematicae", 80:406–424, 1977.
* Larry J. Stockmeyer. The set basis problem is NP-complete. Technical Report RC-5431, IBM, 1975.

ee also

List of NP-complete problems

External Links

[http://11011110.livejournal.com/134829.html blog entry about bipartite dimension by David Eppstein]