I have a graph consisting of about 5000 vertices, with density around 0.5. I'm trying to find two disjoint 6-cliques, which are not connected by an edge. I have tried bruteforcing this, by firstly looking for any 6-cliques, and then checking pairs for being non-adjacent. However, although it finds a lot of 6-cliques it is too slow to find a non-adjacent pair. Is there a faster way to do this?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
Here is one approach:
Find any 6-clique, call it $C$.
Find all vertices that aren't adjacent to any vertex in $C$. Mark them red.
Find a 6-clique among the red vertices.
How long will this take? Let's analyze the running time of each step.
You should be able to find a 6-clique by randomly sampling $2^{15}$ possible ways to choose 6 vertices and checking whether it forms a clique; a random collection of 6 vertices has a $1/2^{{6 \choose 2}} = 1/2^{15}$ probability of being a clique, so you're likely to find one in this way after about $2^{15}$ trials. There are faster ways to find a 6-clique, but this will already be very fast.
This can be done in $6 \times 5000$ operations, i.e., very fast.
Now you have the problem of finding a 6-clique in a smaller graph. How many red vertices do you expect to have? If you pick a vertex at random, then it has a $1/2^6$ probability of being red. Therefore, we expect about $(5000-6)/2^6 \approx 78$ red vertices. It is very likely that a 6-clique exists among them, as there are ${78 \choose 6} \approx 2^{28}$ possible ways to choose a subset of 6 nodes, and each one has about a $1/2^{15}$ chance of being a 6-clique. You can find a 6-clique among the red vertices in the same way as before (randomly choosing a collection of 6 red vertices and checking to see if they form a clique). This takes about $2^{15}$ trials.
So all in all you expect this to be successful, and to take about $2^{16}$ trials, where each trial is very fast. So this algorithm should be very fast. There are probably ways to optimize it further, by using standard algorithms for finding a clique more efficiently than brute force, but I'd guess this should already be adequate, and it has the advantage of being easy to implement.
