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?

  • 4
    $\begingroup$ This is well-known vertex cover approximation $\endgroup$
    – Laakeri
    Oct 2 '21 at 9:24
  • 4
    $\begingroup$ 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$. $\endgroup$ Oct 2 '21 at 19:43
  • 3
    $\begingroup$ 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). $\endgroup$ Oct 2 '21 at 20:41
  • $\begingroup$ @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. $\endgroup$ Oct 3 '21 at 6:54

Your Answer

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

Browse other questions tagged or ask your own question.