Boost logo

Boost :

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> 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> 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> 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> 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> I've placed the tarball at
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 :)


 Jeremy Siek www:
 Ph.D. Candidate email: jsiek_at_[hidden]
 Univ. of Notre Dame work phone: (219) 631-3906

Boost list run by bdawes at, gregod at, cpdaniel at, john at