0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I would say that even if you had had enough reputation to comment, making this follow-up question would have been the better choice - this way, someone can write an answer to it :) $\endgroup$ Nov 11, 2017 at 23:37
  • $\begingroup$ @MishaLavrov Agreed! Awesome answer btw! $\endgroup$
    – Skillzore
    Nov 12, 2017 at 0:01

1 Answer 1

1
$\begingroup$

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}|$.

$\endgroup$
2
  • $\begingroup$ Nice! I'm guessing there is a typo in 1, but I will accept this any way since it answered my question perfectly. Thanks! $\endgroup$
    – Skillzore
    Nov 11, 2017 at 23:59
  • $\begingroup$ Now there is no more typo. $\endgroup$ Nov 12, 2017 at 0:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .