# How to prove the performance ratio of the approximation algorithm of maximum clique is unbounded

Consider the following approximation algorithm for the problem of finding a maximum clique in a given graph $$G$$. Repeat the following step until the resulting graph is a clique. Delete from $$G$$ a vertex that is not connected to every other vertex in $$G$$ and also delete all its incident edges. Show that this greedy approach does not always result in a clique of maximum size. Show that the performance ratio of the approximation algorithm is unbounded. I know it will take maximum $$n-1$$ so, $$O(n)$$, but how to prove that the performance ratio of the approximation algorithm is unbounded?

I found a proof for the following approximation algorithm of the maximum independent set which is similar to the maximum clique, this is the algorithim:

Greedy(G):
S = {}
While G is not empty:
Let v be a node with minimum degree in G
S = union(S, {v})
remove v and its neighbors from G
return S


They proved the performance of that algorithm with the following:

The algorithm has an approximation ratio of $$\Delta + 1$$, where $$\Delta$$ is the maximum degree of the input graph $$G$$. That is, the resultant independent set, denoted as $$S$$, satisfies $$|S| \geq \frac{1}{\Delta + 1} |\mathsf{OPT}|$$, where $$\mathsf{OPT}$$ is a maximum independent set. Below is a proof.

Proof. Let $$V$$ be the set of vertices of $$G$$. To show that $$|S| \geq \frac{1}{\Delta + 1}|\mathsf{OPT}|$$, we only need to show $$|S| \geq \frac{1}{\Delta + 1} |V|$$ For each vertex $$v \in V \backslash S$$, it is removed in the algorithm because some other vertex $$u$$ is put into $$S$$. Note that $$v$$ must be a neighbor of $$u$$ in this case. Charge $$v$$ to $$u$$. Therefore, the size of $$V\backslash S$$ satisfies $$|V \backslash S| = |V| - |S| \leq \Delta |S|$$ which implies $$|V| \leq (1 + \Delta)|S| \Rightarrow |S| \geq \frac{1}{1 + \Delta}|V| \Rightarrow |S| \geq \frac{1}{1 + \Delta}|\mathsf{OPT}|$$

I don't know if I can prove that the performance ratio of the approximation algorithm of maximum clique is unbounded using exactly this proof or not.

• – D.W.
Dec 21, 2022 at 23:26
• @D.W. I don't know what is the correct place ..
– RJ94
Dec 21, 2022 at 23:35
• That is not an acceptable reason for posting on multiple sites. Read the help pages for each site and make your best guess. If you can't tell, pick one, and if you later discover you posted on the wrong site, delete that copy before posting it elsewhere.
– D.W.
Dec 21, 2022 at 23:36
• okay, sorry for that
– RJ94
Dec 21, 2022 at 23:41