Re: [boost] BGL: max clique?

From: Doug Gregor (gregod_at_[hidden])
Date: 2001-03-04 13:14:46

On Sunday 04 March 2001 02:10, Phlip wrote:
> Boosters:
>
> Does Boost Graph Library have any algorithms to locate the maximum clique
> in a graph?

Unless the authors of the Boost Graph library are hiding something, no.

> (A clique is a sub-graph in which every node links to every other node.)
>
> If not, how would one approach this problem?

This problem is _very_ computationally intensive. The maximal clique problem 
is NP-complete already, and the maximum clique problem is even worse (can't 
be verified in polynomial time). In any case, don't expect a polynomial 
algorithm to solve either problem.

For the maximal clique problem, it is possible to achieve a polynomial delay 
between finding maximal cliques (there may be an exponential number of 
maximal cliques). There is a paper titled "A new algorithm for generating all 
the maximal independent sets" by S. Tsukiyama, M. Ide, H. Ariyoshi and I. 
Shirakawa that describes such an algorithm. If you are dealing with graphs 
that are relatively sparse, it may be reasonable to use such an algorithm, 
enumerate all maximal cliques, and then use the clique(s) of maximum size. 

I have an implementation of some derivatives of the original Tsukiyama 
algorithm implemented based on an older version of GGCL (the Boost Graph 
library in a former life). The algorithms implemented are described in the 
paper titled "Local multiple alignment via subgraph enumeration" by Z. Zhang, 
B. He, and W. Miller. The delay between maximal cliques is O(R^4) (where R 
bounds the degree of each node). 

I've placed the tarball at http://www.cs.rpi.edu/~gregod/maxclique.tgz 
The tarball contains the version of GGCL we used along with some sample 
graphs. Porting the algorithm to the Boost Graph library from GGCL should be 
very easy.

        Doug