Ok so given a graph $ \mathrm G = (V,E) $ and we want to find a maximum independent set with the following algorithm:
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
Ok so i can think of examples where this algorithm fails, but can someone give the approximation ratio ? I have a feeling it has something to do with the maximum node degree but i cant figure it out
Best Answer
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}| $$