Re: [boost] BGL: max clique?

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-03-04 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 sub-graph 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 NP-complete 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: [phone]
----------------------------------------------------------------------