<p>The greedy algorithm for the independent set problem works as follows: Pick a node with smallest degree, add it to the independent set, and remove it and all of its neighbors from the graph. Continue until the graph is empty.</p>
<p>If the graph has maximum degree <span class="math-container">$\Delta$</span>, it is easy to see that this algorithm achieves a <span class="math-container">$\Delta$</span> approximation (because for a node and its neighbors the optimal independent set can contain at most <span class="math-container">$\Delta$</span> of those nodes and the greedy algorithm picks one of those nodes).</p>
<p>By a more careful analysis, <a href="https://link.springer.com/article/10.1007/BF02523693" rel="nofollow noreferrer">Halldórsson and Radhakrishnan (1997)</a> show that the greedy algorithm achieves even an <span class="math-container">$(\Delta+2) / 3$</span> approximation.
Moreover, they give an example where the greedy algorithm finds a solution that does <strong>not</strong> achieve an approximation of <span class="math-container">$(\Delta + 2) / 3 - O(\Delta^2 / n)$</span> where <span class="math-container">$n$</span> is the number of nodes.
Therefore, their analysis is almost tight if the maximum degree <span class="math-container">$\Delta$</span> is low.
But the example is of no use if <span class="math-container">$\Delta$</span> approaches <span class="math-container">$n$</span>.</p>
<p><strong>My question:</strong> What is the approximation guarantee when the maximum degree in not bounded? Or in other words, what is the approximation guarantee in terms of <span class="math-container">$n$</span>?
In particular: What is an example of an instance where the greedy algorithm performs poorly (in terms of <span class="math-container">$n$</span>)?</p>
<p>Some additional information:</p>
<p>It is known that for all <span class="math-container">$\epsilon &gt; 0$</span>, the independent set problem cannot be approximated to within <span class="math-container">$n^{1-\epsilon}$</span> unless P = NP (<a href="https://dl.acm.org/doi/abs/10.1145/1132516.1132612" rel="nofollow noreferrer">Zuckermann (2006)</a>).
And, under the unique games conjecture, it cannot be approximated within <span class="math-container">$O(n / \log^2n)$</span> (<a href="https://theoryofcomputing.org/articles/v007a003/" rel="nofollow noreferrer">Austrin et al. (2011)</a>).
Thus, the greedy algorithm cannot be better than this.</p>
<p>But how good is it? Does it achieve only <span class="math-container">$n/3$</span> (as shown by Halldórsson and Radhakrishnan (1997))? If yes, what is an example of a graph where the algorithms is really that bad. Or is the approximation better? Maybe <span class="math-container">$n/4$</span> or <span class="math-container">$n/5$</span> or maybe even <span class="math-container">$n/\log n$</span>?</p>

CC BY-SA 4.0
2024-11-25T12:57:35.247Z
It does not achieve better than $n/4$ approximation. Consider an $n$-vertex graph created by taking an independent set $I$ of size $n/2-1$, a clique $C$ of size $n/2$, whose all vertices are connected to all vertices in $I$, and a vertex $v$ connected to all vertices in $I$. Now, $v$ is the unique vertex of minimum degree, but after taking $v$, we can take only one more vertex, so we produce an independent set of size $2$, while the optimum has size $n/2-1$.
Laakeri
CC BY-SA 4.0
2024-11-25T13:14:54.570Z
Great, this is exactly what I was looking for. Thanks! Do you also know whether n/4 is always achieved?
badboul
<approximation-algorithms><greedy-algorithms><independent-set>
Independent Set: Approximation guarantee of greedy algorithm for graphs without bounded degree
badboul
# Independent Set: Approximation guarantee of greedy algorithm for graphs without bounded degree

(Asked by: username_0 on 2024-11-25)

The greedy algorithm for the independent set problem works as follows: Pick a node with smallest degree, add it to the independent set, and remove it and all of its neighbors from the graph. Continue until the graph is empty.

If the graph has maximum degree $\Delta$, it is easy to see that this algorithm achieves a $\Delta$ approximation (because for a node and its neighbors the optimal independent set can contain at most $\Delta$ of those nodes and the greedy algorithm picks one of those nodes).

By a more careful analysis, [Halldórsson and Radhakrishnan (1997)](https://link.springer.com/article/10.1007/BF02523693) show that the greedy algorithm achieves even an $(\Delta+2) / 3$ approximation.
Moreover, they give an example where the greedy algorithm finds a solution that does **not** achieve an approximation of $(\Delta + 2) / 3 - O(\Delta^2 / n)$ where $n$ is the number of nodes.
Therefore, their analysis is almost tight if the maximum degree $\Delta$ is low.
But the example is of no use if $\Delta$ approaches $n$.

**My question:** What is the approximation guarantee when the maximum degree in not bounded? Or in other words, what is the approximation guarantee in terms of $n$?
In particular: What is an example of an instance where the greedy algorithm performs poorly (in terms of $n$)?

Some additional information:

It is known that for all $\epsilon > 0$, the independent set problem cannot be approximated to within $n^{1-\epsilon}$ unless P = NP ([Zuckermann (2006)](https://dl.acm.org/doi/abs/10.1145/1132516.1132612)).
And, under the unique games conjecture, it cannot be approximated within $O(n / \log^2n)$ ([Austrin et al. (2011)](https://theoryofcomputing.org/articles/v007a003/)).
Thus, the greedy algorithm cannot be better than this.

But how good is it? Does it achieve only $n/3$ (as shown by Halldórsson and Radhakrishnan (1997))? If yes, what is an example of a graph where the algorithms is really that bad. Or is the approximation better? Maybe $n/4$ or $n/5$ or maybe even $n/\log n$?

**Tags:** approximation-algorithms, greedy-algorithms, independent-set
> **Comments:**
> **username_1**: It does not achieve better than $n/4$ approximation. Consider an $n$-vertex graph created by taking an independent set $I$ of size $n/2-1$, a clique $C$ of size $n/2$, whose all vertices are connected to all vertices in $I$, and a vertex $v$ connected to all vertices in $I$. Now, $v$ is the unique vertex of minimum degree, but after taking $v$, we can take only one more vertex, so we produce an independent set of size $2$, while the optimum has size $n/2-1$.  
> **username_0**: Great, this is exactly what I was looking for. Thanks! Do you also know whether n/4 is always achieved?  

---

## 0 answers

