Re: [boost] BGL: max clique?

From: Doug Gregor (gregod_at_[hidden])
Date: 2001-03-04 15:19:54

On Sunday 04 March 2001 01:24, Phlip wrote:
> Proclaimed Doug Gregor from the mountaintops:
> > 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.
>
> Oops. What's the difference between "maximal" and "maximum". Maybe the
> first is "find all nested KGraphs with a node count > X", and the second is
> "what's the biggest one?"
>
> I just whipped out my /Combinatorics for Dummies/ book but it didn't have
> it.

A maximal clique is a clique that is not contained in any other clique, 
whereas a maximum clique is a maximal clique of maximum size. Maximal does 
not imply maximum - for instance, take a graph with four nodes (w, x, y, z) 
where {x, y, z} is a maximal clique and {w} is also a maximal clique. Only 
{x, y, z} is a maximum clique.

> > I've placed the tarball at http://www.cs.rpi.edu/~gregod/maxclique.tgz
>
> Yes! Thanks!
>
> The good news is our algorithmicist at work is about to blow your max
> clique algorithm out of the water. But the other good news is it's
> proprietary, so you'l have to either jump ship or wait 20 years to see how
> we did it. :-)

Hmmm. Depending on the the definition of blowing an algorithm out of the 
water, I'm not sure what you say is possible... If the maximum clique problem 
could be solved in polynomial time, then the k-clique problem ("given a graph 
G and a number k, does G have a k-clique" - this is an NP-complete problem) 
could be solved in polynomial time just be using the maximum clique algorithm 
and comparing k to the size of the maximum clique... This this hasn't been 
proven impossible, this would mean that P = NP (class of polynomially 
solvable algorithms = class of polynomially verifiable algorithms) - which 
would be a surprising result, to say the least.

Now, I don't even think the maximum clique problem is in NP, because I don't 
see how it could be verified in polynomial time: Take any clique C that is 
claimed to be maximum. The only way we can tell if C is maximum is if we make 
sure no larger clique exists - but this requires solving the exact same 
superpolynomial problem to find the maximum clique.

There may, of course, be faster algorithms for enumerating maximal cliques 
that in practice have smaller constants or better asymptotic behavior. Also, 
of course, there may be algorithms specifically designed to get a maximum 
clique that could do better. 

        Doug