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

Jerad

@poly: en.wikipedia.org/wiki/Clique_number#Definitions – Riccio

clique number is the number of vertices in the maximum clique. – Jerad

Thanks for the UVA link; I'll try to work on this over the weekend. Note that the problem is in Brute Force/Backtracking - Easy categories, however: uva.onlinejudge.org/… – Exuviae

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.

Exuviae

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.

Ewers

Answer 3

Although the problem is NP-hard, the size of graph you mention is not any problem for today´s fastest maximum clique exact solvers (for any configuration).

If you are ready to implement the code then I recommend you read the papers connected with the family of algorithms MCQ, MCR and MCS, as well as the family BBMC, BBMCL and BBMCX. An interesting starting point is the comparison survey by Prosser [Prosser 12]. It includes explanation for a Java implementation of these algorithms.

Blader