From: Doug Gregor (gregod_at_[hidden])
Date: 2001-03-04 13:14:46
On Sunday 04 March 2001 02:10, Phlip wrote:
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk