Expected number of nodes in the independent set produced by a coloring algorithm on a graph with maximal degree $k$

Question

We have a graph with $n$ nodes and maximal degree $k$. On this graph we run a coloring algorithm that finds a maximum independent set. The algorithm colors every node green with probability $\frac{1}{k}$ and colors the node red otherwise. This is done independently for every node. Return the independent set of nodes $x$ where $x$ is green and all neighbors of $x$ are red.

1. Show that the expected number of nodes in the independent set is at least $\frac{cn}{k}$ where $c$ is some constant. (That is, $c$ does not depend on $k$).

2. Prove that the expected approximation ratio of the algorithm is at least $\frac{c}{k}$

I have no idea where to start on showing this.

I think I have figured out that the algorithm fails with probability $1-(1-\frac{1}{k})^k$ and that for any fixed node the probability for that node being put in the independent set is $\frac{1}{k}(1-\frac{1}{k})^k$. I am not sure, however, that these results are completely correct. That might be the reason I can't find a way of showing this or I could be missing something obvious. Help would be appreciated.

For anyone wondering, this is a practice problem for an upcoming exam.

Answer 1

As you've computed the probability of a node be in the dependent set is $\frac{1}{k}(1-\frac{1}{k})^k$. Hence, the expected number of these nodes is $n\frac{1}{k}(1-\frac{1}{k})^k$. As $\frac{1}{e} \leq \frac{1}{k}(1-\frac{1}{k})^k$, so the expected would be at least $\frac{cn}{k}$ (for $\frac{1}{e} \geq c$).

Hence, the expected approximation ratio is $\frac{cn}{k}$ over $n$.