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

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.

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$.
• What is $1/e$ supposed to be here? Or rather, what is $e$? – Skillzore Jan 10 '18 at 15:52
• @Skillzore As you know, $(1-\frac{1}{k})^k$ for $k \to \infty$ is equal to $\frac{1}{e}$ – OmG Jan 10 '18 at 16:47