# Large CLIQUE approximation

I am interested in algorithms to identify large cliques in graphs where the largest clique is a large fraction (definitely greater than half, perhaps as great as 4/5) of the total number of vertices.

Here is an example of a randomized algorithm which is the best I could think of for now. Supposing that there are $$|V|$$ vertices, and the max clique is of size $$|V| - k$$ this returns a clique of size around $$|V| - 2k$$ with high probability, which is nontrivial if $$k < |V|/2$$ and approaches $$|V|$$ itself as $$k$$ shrinks.

Starting with the set of all vertices, arbitrarily choose pairs with no edge, then eliminate one member at random, and repeat until you have a clique.

Since one of the members of each conflicting pair must be outside the maximum clique, the expected number of vertices outside the clique removed after $$2k$$ iterations is at least $$k$$. We can therefore expect the algorithm to terminate in $$2k$$ rounds or so (with a concentration inequality argument and some leeway). This leaves us with a clique of the size mentioned above.

Is there a way to make this algorithm deterministic? Can we do better than this ~twofold expansion in the size of the "bad" vertices?

• This is well-known vertex cover approximation Oct 2, 2021 at 9:24
• Max clique is very hard to approximate even when the largest clique size is a constant factor of $n$. However if the clique size is more than $(3/4 + \delta) n$ for some $\delta > 0$ then you can use the following fact. Consider the complement graph $\bar{G}$. Compute a simple $2$-approximation to the vertex cover of $\bar{G}$, say $S$, and $V-S$ would be an independent set of size $(1/2+2\delta)n$ which would be a clique in $G$. Oct 2, 2021 at 19:43
• I guess it suffices to assume that the clique size in $G$ is at least $(1/2+\delta)n$ rather than $(3/4+\delta)n$ as I wrote above. Basically as long as a $2$-approximation for vertex cover ensures that it doesn't trivially take all vertices, one should get a good approximation for independent set (and hence clique). Oct 2, 2021 at 20:41
• @Laakeri and Chandra, Thanks for pointing out the vertex-cover framing I was missing - it gives me a good jumping off point. I see now how the randomization I was doing was unnecessary. Oct 3, 2021 at 6:54