Chromatic characterization of biclique covers

AbstractA biclique B of a simple graph G is the edge-set of a complete bipartite subgraph of G. A biclique cover of G is a collection of bicliques covering the edge-set of G. Given a graph G, we will study the following problem: find the minimum number of bicliques which cover the edge-set of G. This problem will be called the minimum biclique cover problem (MBC). First, we will define the families of independent and dependent sets of the edge-set E(G) of G: F⊆E(G) will be called independent if there exists a biclique B⊆E(G) such that F⊆B, and will be called dependent otherwise. From our study of minimal dependent sets we will derive a 0–1 linear programming formulation of the following problem: find the maximum weighted biclique in a graph. This formulation may have an exponential number of constraints with respect to the number of nodes of G but we will prove that the continuous relaxation of this integer program can be solved in polynomial time. Finally we will also study continuous relaxation methods for the problem (MBC). This research was motivated by an open problem of Fishburn and Hammer