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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.