4
$\begingroup$

enter image description here

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?

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Tom van der Zanden Jan 1 '15 at 11:31
  • $\begingroup$ 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. $\endgroup$ – Panpan Jan 1 '15 at 13:29
  • 1
    $\begingroup$ 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.) $\endgroup$ – D.W. Mar 3 '15 at 1:08
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.