<p>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.</p>
<p>Here is an example of a randomized algorithm which is the best I could think of for now. Supposing that there are <span class="math-container">$|V|$</span> vertices, and the max clique is of size <span class="math-container">$|V| - k$</span> this returns a clique of size around <span class="math-container">$|V| - 2k$</span> with high probability, which is nontrivial if <span class="math-container">$k &lt; |V|/2$</span> and approaches <span class="math-container">$|V|$</span> itself as <span class="math-container">$k$</span> shrinks.</p>
<p>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.</p>
<p>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 <span class="math-container">$2k$</span> iterations is at least <span class="math-container">$k$</span>. We can therefore expect the algorithm to terminate in <span class="math-container">$2k$</span> rounds or so (with a concentration inequality argument and some leeway). This leaves us with a clique of the size mentioned above.</p>
<p>Is there a way to make this algorithm deterministic? Can we do better than this ~twofold expansion in the size of the &quot;bad&quot; vertices?</p>

CC BY-SA 4.0
2021-10-02T09:24:44.990Z
This is well-known vertex cover approximation
Laakeri
CC BY-SA 4.0
2021-10-02T19:43:31.427Z
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$.
Chandra Chekuri
CC BY-SA 4.0
2021-10-02T20:41:09.823Z
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).
Chandra Chekuri
CC BY-SA 4.0
2021-10-03T06:54:16.110Z
@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.
Bolton Bailey
<reference-request><approximation-hardness><clique>
Large CLIQUE approximation
Bolton Bailey
# Large CLIQUE approximation

(Asked by: username_0 on 2021-10-02)

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?

**Tags:** reference-request, approximation-hardness, clique
> **Comments:**
> **username_1**: This is well-known vertex cover approximation  
> **username_2**: 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$.  
> **username_2**: 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).  
> **username_0**: @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.  

---

## 0 answers

