The approximation ratio of a maximum independent set, max degree instead of max degree + 1

Question

While reading this answer about the approximation ratio of a maximum independent set, I had a follow up question but not enough reputation to comment. So instead I made this question.

Keeping the proof in the previously mentioned answer in mind, can't we somehow argue that instead of $|S| \geq \frac{1}{\Delta + 1}|V|$, that actually $|S| \geq \frac{1}{\Delta}|V|$?

It is just something that my lecturer in my algorithms course mentioned, but I can't quite see the way to argue it. He said something like: "Assign every node not being in S arbitrarily to one neighbor in S, and then study where the nodes of V may be located."

Any ideas?

Answer 1

We cannot argue that $|S| \ge \frac1{\Delta} |V|$, but we can argue that $|S| \ge \frac1{\Delta} |\mathsf{OPT}|$ (where $\mathsf{OPT}$ is an optimal independent set), assuming $\Delta \ge 1$.

To do this, the only property of $S$ we need is that it is a maximal independent set: there is no larger independent set containing $S$.

Partition $V$ into $|S|$ many subsets $V_1, V_2, \dots, V_{|S|}$ as follows:

1. Order the elements of $S$ arbitrarily as $s_1, s_2, \dots, s_k$ (so that $k = |S|$).
2. For each $i=1,\dots,k$, let $V_i = \{s_i\}$ to begin with.
3. For every $v \in V \setminus S$, choose an arbitrary $s_i \in S$ adjacent to $v$, and add $v$ to $V_i$. (If no such $s_i$ existed, $S$ would not be maximal.)

The size of each $V_i$ is at most $\Delta+1$: $V_i$ includes only $s_i$ and the neighbors of $s_i$, of which there are at most $\Delta$. Moreover, $|V_i \cap \mathsf{OPT}| \le \Delta$: either $\mathsf{OPT}$ includes $s_i$ (and no other elements of $V_i$) or it includes some number of the other elements (at most $\Delta$), but not $s_i$.

So while $|S| = k$, we have $$|\mathsf{OPT}| = \sum_{i=1}^k |\mathsf{OPT} \cap V_i| \le \sum_{i=1}^k \Delta = \Delta k$$ and therefore $|S| = k \ge \frac1{\Delta}|\mathsf{OPT}|$.