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).

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\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$.

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.

INSTANCE: A collection of finite sets $S_{1},\ldots ,S_{n}$ and a positive integer $k$.

QUESTION: Can we choose at most $k$ subsets such that their union equals $\bigcup _{i=1}^{n}S_{i}$, the union of all $S_{i}$?

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. Computers and Intractability: A Guide to the Theory of NP-Completeness. 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.

See also

List of NP-complete problems

External Links

blog entry about bipartite dimension by David Eppstein