This question is quite specific and practical. I hope it is still relevant for MO and will not be removed.

I have a collection $\mathcal{C}$ of graphs having from 5000-6000 vertices and edge density about $0.5,$ the average degree being quite close to half the number of vertices.

I need to determine whether a graph $G \in \mathcal{C}$ has a clique greater than some given constant $k$, for my purpose I can assume $k = 50.$

Using cliquer on these graphs does not produce any result in a reasonable amount of time and since it is not required that I compute the clique number exactly I improvised the following way to test whether a graph has a clique of size $> k$ or not.

A vertex $v$ of $G$ is *uninvolved* if $v$ is not contained in a clique of size $> k.$

Observe that if $v$ is uninvolved then $G$ has a large clique if and only if $G-v$ has.

Note also that $v$ is uninvovled if and only if the clique number of the graph induced by $N(v)$ is not greater than $k-2.$ This gives us a recursive way of determing whether our graph has a large clique or not.

Now, I've noticed that the graphs in $\mathcal{C}$ have quite some amount of symmetry. They are far from being vertex transitive, but their automorphism group partitions the vertex set into orbits of nice size and hence one can use the following idea.

Pick a vertex $v$ such that $N(v)$ is small.

2.1 If the graph induced by $N(v)$ has a large clique report it.

2.2 Let $\mathcal{O}$ be the orbit of $v$ in $G.$ Test if $G-\mathcal{O}$ has a large clique.

The above is implemented as a Sage program here.

The described method works fine but is still too slow given that I need to test this on a large collection of graphs. I've read some literature about cliques and the respective upper bounds but I was not able to find a good bound or practical method for the graphs in $\mathcal{C}.$ The only property that I am thus able to exploit is their symmetry.

My question therefore is

- Are there any other invariants I could check to speed up the above computation?
- Is there any other that works well when one only needs to verify whether a certain graph has a large clique or not?
- Are there any other approaches you for solving this efficiently?

**Edit.** Here is one example of a graph given as a list of edges.

MaxCliqueDynto be found at sicmm.org/~konc/maxclique often supersedescliquer. Maybe it helps in your situation. $\endgroup$ – Peter Mueller Mar 17 '14 at 11:12SODA. 1998. $\endgroup$ – Joseph O'Rourke Mar 17 '14 at 18:259more comments