In the mathematical fields of graph theory and combinatorial optimization, the bipartite dimension or biclique cover number 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: The bipartite dimension of the n-vertex complete graph,
The bipartite dimension of a 2n-vertex crown graph equals
, where is the inverse function of the central binomial coefficient (de Caen, Gregory & Pullman 1981).
Fishburn & Hammer (1996) determine the bipartite dimension for some special graphs.
The computational task of determining the bipartite dimension for a given graph G is an optimization problem.
The set basis problem is now given as follows: In its former formulation, the problem was proved to be NP-complete by Orlin (1977), even for bipartite graphs.
The formulation as a set basis problem was proved to be NP-complete earlier by Stockmeyer (1975).
The problem remains NP-hard even if we restrict our attention to bipartite graphs whose bipartite dimension is guaranteed to be at most
, with n denoting the size of the given problem instance (Gottlieb, Savage & Yerukhimovich 2005).
On the positive side, the problem is solvable in polynomial time on bipartite domino-free graphs (Amilhastre, Janssen & Vilarem 1997).
Indeed, the bipartite dimension is NP-hard to approximate within
, already for bipartite graphs (Gruber & Holzer 2007).
In contrast, proving that the problem is fixed-parameter tractable is an exercise in designing kernelization algorithms, which appears as such in the textbook by Downey & Fellows (1999).
Fleischner et al. (2009) also provide a concrete bound on the size of the resulting kernel, which has meanwhile been improved by Nor et al. (2010).
In fact, for a given bipartite graph on n vertices, it can be decided in time
whether its bipartite dimension is at most k (Nor et al. 2010) The problem of determining the bipartite dimension of a graph appears in various contexts of computing.
In a role-based access control system, a role provides access rights to a set of resources.
Also, a role can be owned by multiple users.
The set of users together with the set of resources in the system naturally induces a bipartite graph, whose edges are permissions.
Each biclique in this graph is a potential role, and the optimum solutions to the role mining problem are precisely the minimum biclique edge covers (Ene et al. 2008).
In that setup, several messages need to be sent each to a set of receivers, over an insecure channel.
Each message has to be encrypted using some cryptographic key that is known only to the intended receivers.
Each receiver may possess multiple encryption keys, and each key will be distributed to multiple receivers.
The optimum key generation problem is to find a minimum set of encryption keys for ensuring secure transmission.
As above, the problem can be modeled using a bipartite graph whose minimum biclique edge covers coincide with the solutions to the optimum key generation problem (Shu, Lee & Yannakakis 2006).
A different application lies in biology, where minimum biclique edge covers are used in mathematical models of human leukocyte antigen (HLA) serology (Nau et al. 1978).