2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

Here is one approach:

  1. Find any 6-clique, call it $C$.

  2. Find all vertices that aren't adjacent to any vertex in $C$. Mark them red.

  3. Find a 6-clique among the red vertices.

How long will this take? Let's analyze the running time of each step.

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

  2. This can be done in $6 \times 5000$ operations, i.e., very fast.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.