0
$\begingroup$

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.

$\endgroup$
4

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.