[Math] Determine if a graph has a large clique

algorithmsco.combinatoricsgraph theorysoft-question

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.

  1. 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

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

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

Best Answer

One can compute upper bounds (which are sometimes tight) on the size of cliques in $G$.

A standard trick would be to compute Lovasz $\theta$-function $\theta(G)$ of $G$ (or a slightly better, Schrijver's variant of $\theta$, usually called $\theta'$), or some (weaker in general) upper bound on the clique number. This is a particular kind of a semidefinite programming problem. I have Sage code that can in principle be used for this – I have not found time (or a student to work on this) to properly include it into Sage. For graphs of this size it is however a challenge to make it run fast enough. (There are a number of stand-alone implementations of this computation available, too).

Using symmetries might reduce the size of the problem quite considerably - you would basically need one variable per edge/non-edge orbit of your automorphism group.

Of course there is no guarantee that it will be useful, as it could only (potentially) rule out existence of $k$-clique in $G$, by establishing that $\theta'(G)$ < $k$.

Related Question