Determine if a graph has a large clique

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.

Answer 1

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

Answer 2

Determining, even approximately, the largest clique in a graph is known to be NP-hard. You cannot determine with any degree of accuracy the largest clique for a given graph in polynomial time.

From this:

Definition 2.2. GapCLIQUE ρ :Given ρ ≤ 1, a graph G and an integer k, we wish to distinguish between the following two cases:

YES: ω(G) ≥ k, G has a clique of size k

NO: ω(G) < ρk, G has no clique of size ≥ ρk.

Theorem 2.7. ∀ ρ > 0, GapCLIQUE is NP -hard.

Answer 3

May be more relevant than hardness of approximation results is the fact that finding a clique of size $k$ is complete for the class W[1]. This means that an algorithm with running time $f(k)\cdot n^c$ is unlikely to exist, where $f$ is a function independent of $n$ and $c$ is a constant independent of $k$. Particularly, if such an algorithm existed, then 3SAT would be solvable in time $2^{o(n)}$, which contradicts the Exponential Time Hypothesis (ETH), and would be a fairly big surprise. In fact we even know that an algorithm with running time $f(k)\cdot n^{o(k)}$ already contradicts ETH. For background on ETH and this type of negative results you can also check this nice survey by Lokshtanov, Marx, and Saurabh.

Answer 4

This is a simple idea and I'm not sure how useful it will be, but I'll throw it in anyway. Call your current graph $G$. If $G$ has a vertex $v$ of low degree, you can eliminate it and its orbit quickly, and if not then the algorithm gets bogged down. So when there are no vertices of low degree left, it might be worth instead looking for vertices $v$ such that $G[N(v)]$ has many vertices of low degree. Thus the algorithm will be able to eliminate a lot of vertices from $G[N(v)]$ quite quickly in the recursive step, and hopefully $v$ itself will be eliminated quite quickly. Of course this will add a lot of overhead, so it might not be worth the trade-off.