
Boost : 
From: Jeremy Siek (jsiek_at_[hidden])
Date: 20010304 13:21:09
On Sun, 4 Mar 2001, Doug Gregor wrote:
gregod> On Sunday 04 March 2001 02:10, Phlip wrote:
gregod> > Boosters:
gregod> >
gregod> > Does Boost Graph Library have any algorithms to locate the maximum clique
gregod> > in a graph?
gregod>
gregod> Unless the authors of the Boost Graph library are hiding
gregod> something, no.
No, we don't have a max clique algorithm.
gregod> > (A clique is a subgraph in which every node links to every other node.)
gregod> >
gregod> > If not, how would one approach this problem?
gregod>
gregod> This problem is _very_ computationally intensive. The maximal clique problem
gregod> is NPcomplete already, and the maximum clique problem is even worse (can't
gregod> be verified in polynomial time). In any case, don't expect a polynomial
gregod> algorithm to solve either problem.
gregod>
gregod> For the maximal clique problem, it is possible to achieve a polynomial delay
gregod> between finding maximal cliques (there may be an exponential number of
gregod> maximal cliques). There is a paper titled "A new algorithm for generating all
gregod> the maximal independent sets" by S. Tsukiyama, M. Ide, H. Ariyoshi and I.
gregod> Shirakawa that describes such an algorithm. If you are dealing with graphs
gregod> that are relatively sparse, it may be reasonable to use such an algorithm,
gregod> enumerate all maximal cliques, and then use the clique(s) of maximum size.
gregod>
gregod> I have an implementation of some derivatives of the original Tsukiyama
gregod> algorithm implemented based on an older version of GGCL (the Boost Graph
gregod> library in a former life). The algorithms implemented are described in the
gregod> paper titled "Local multiple alignment via subgraph enumeration" by Z. Zhang,
gregod> B. He, and W. Miller. The delay between maximal cliques is O(R^4) (where R
gregod> bounds the degree of each node).
gregod>
gregod> I've placed the tarball at http://www.cs.rpi.edu/~gregod/maxclique.tgz
gregod> The tarball contains the version of GGCL we used along with some sample
gregod> graphs. Porting the algorithm to the Boost Graph library from GGCL should be
gregod> very easy.
If someone were to do this port and write docs, it would certainly make
a nice addition to the BGL :)
Cheers,
Jeremy

Jeremy Siek www: http://www.lsc.nd.edu/~jsiek/
Ph.D. Candidate email: jsiek_at_[hidden]
Univ. of Notre Dame work phone: (219) 6313906

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk