clique number of a graph

Question

I would like to know a fast algorithm to find only the clique number(without actually finding the clique) of a graph with about 100 vertices.

I am trying to solve the following problem. http://uva.onlinejudge.org/external/1/193.html

Answer 1

This is NP-complete, and you can't do it much better than actually finding the maximum clique and counting its vertices. From Wikipedia:

Clique problems include:

• solving the decision problem of testing whether a graph contains a clique larger than N

These problems are all hard: the clique decision problem is NP-complete (one of Karp's 21 NP-complete problems),

If you can find the clique number in P, then the decision problem is answerable in P (you simply compute the clique number and compare it with N).

Since the decision problem is NP-Complete, finding the clique number of a general graph must be NP-Hard.

Answer 2

As already stated by others, this is probably really hard.

But like many theoretically hard problems, it can be pretty fast in practice with a good algorithm and suitable data. If you implement something like Bron-Kerbosch for finding cliques, while keeping track of the largest clique size you've found so far, then you can backtrack out of fruitless search trees.

For example, if you find a clique with 20 nodes in it, and your network has a large number of nodes with degree less than 20, you can immediately rule out those nodes from further consideration. On the other hand, if the degree distribution is more uniform, then this might be as slow as finding all the cliques.