On the generation of bicliques of a graph ?
An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B  is a subset of vertices admitting a bipartition B=X?Y B = X ? Y , such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y . If both X,Y?? X , Y ? ? , then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. When the requirement that X and Y are independent sets of G is dropped, we have a non-induced biclique. We show that it is NP-complete to test whether a subset of the vertices of a graph is part of a biclique. We propose an algorithm that generates all non-induced bicliques of a graph. In addition, we propose specialized efficient algorithms for generating the bicliques of special classes of graphs.
biclique np-complete algorithms enumeration polynomial time delay convex bipartite graphs