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

cs.stackexchange https://cs.stackexchange.com/questions/86524

Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top