Bipartite Dimension - Computing The Bipartite Dimension

Computing The Bipartite Dimension

The computational task of determining the bipartite dimension for a given graph G is an optimization problem. The decision problem for bipartite dimension can be phrased as:

INSTANCE: A graph and a positive integer .

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

This problem appears as problem GT18 in Garey and Johnson's classical book on NP-completeness, and is a rather straightforward reformulation of another decision problem on families of finite sets.

The set basis problem appears as problem SP7 in Garey and Johnson's book. Here, for a family of subsets of a finite set, a set basis for is another family of subsets of, such that every set can be described as the union of some basis elements from . The set basis problem is now given as follows:

INSTANCE: A finite set, a family of subsets of, and a positive integer k.

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

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

Regarding the existence of approximation algorithms, Simon (1990) proved that the problem cannot be approximated well (assuming P ≠ NP). Indeed, the bipartite dimension is NP-hard to approximate within for every fixed, 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, Mujuni & Szeider (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 with whether its bipartite dimension is at most k (Nor et al. 2010)