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

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?

• Wouldn't a very trivial solution to this problem be to return all the edges of the graph? Every edge is a (bi)clique, and together they cover the graph. – Tom van der Zanden Jan 1 '15 at 11:31
• yes, that will be one solution, i am trying to look for non trivial solutions such as those with minimum numbers of cliques and bicliques. – Panpan Jan 1 '15 at 13:29
• If Tom van der Zanden's answer is not an acceptable solution, then I think you should edit your question to indicate exactly what problem you are trying to solve. Don't just drop clarifications in the comments -- edit your question so that it will be clear to someone who reads only the text of your question. (Comments exist only to help you improve your question, and readers shouldn't have to read the comments to understand what you are asking.) – D.W. Mar 3 '15 at 1:08

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