Existing technique to detect the clique and biclique cover the edges in a graph?

Question

I wonder if there is any existing method to find the clique and biclique structures in a graph that can cover all the edges in it, and every edge belongs to exactly one of the cliques or bicliques found? I try to illustrate the idea in the figure above where the red edges belong to a biclique and the blue edges belong to a clique. All the edges in the graph are covered by the structures found.

The bicliques and cliques may have overlapping nodes.

The motivation of doing this is that in social networks, the biclique structure often corresponds to an influential group of persons that reach a common group of audiences, and such structural feature cannot be described by clique ...

As noted by Tom van der Zanden, a trivial solution would be to return all the edges of the graph. I am trying to look for non trivial solutions such as those with minimum numbers of cliques and bicliques.

I wonder if anybody could point to some research in this area?

Answer 1

In case the input graph is bipartite, all cliques in the cover must be bicliques. Thus for bipartite graphs the problem that you are describing is the biclique partition problem. The biclique partition problem (and hence the more general problem that you describe) is NP-complete, and is NP-hard to approximate within $n^{1-\epsilon}$ for every $\epsilon>0$.

See here for more details: P. Chalermsook, S. Heydrich, E. Holm, A. Karrenbauer: Nearly Tight Approximability Results for Minimum Biclique Cover and Partition. In: Proceedings of 22th Annual European Symposium on Algorithms (ESA), LNCS 8737, 2014, pp. 235-246

EDIT: Some easy combinatorial bounds: Let $opt(G)$ denote the minimum number of cliques/bicliques in an edge partition. Then $opt(G)$ is at most the chromatic number of the complement graph $\overline G$. Also, if $bp(G)$ denotes the number of bicliques in a minimum biclique edge partition of $G$, then $opt(G)\le bp(G)$.

If you are interested in implementing a solution... Whereas you cannot resort to approximations, then you can still use some preprocessing and a greedy heuristic. In a preprocessing step, you can put all twin vertices, i.e. pairs of vertices that have the same set of neighbors, into equivalence classes. For the heuristic, call a heuristic for maximum clique, and one for maximum biclique. If the number of edges in the biclique we found is larger than that of the found clique, add the biclique to the edge cover, remove all edges in the biclique, and continue with the remaining graph. Otherwise, we add the clique to the edge cover and proceed in a similar manner.