I am doing an exercise related to maximizing Independent Set, I have $G = (V = \{v_1, . . . , v_n\}, E)$ as an undirected graph. This graph as $n!$ possible orderings for the vertices $V$.

If we pick any such orderings uniformly at random i.e. let $\sigma = (\sigma_1, . . . , \sigma_n)$ be such random ordering then consider :

Begin with $S = \emptyset$.

Then, at each step for $i = 1$ to $n$, if for all $u \in S$, $(u, v_{\sigma_i}) \notin E$, add $v_{\sigma_i}$ to $S$.

Suppose we denote by $d$ the maximum degree of a vertex in $V$. We need to prove that the proposed algorithm achieves an independent set with expected value of at least $1/d$ fraction of the optimal solution.

My Proposed incomplete solution:

We denote OPT solution as $S^*$ and $|S^*| = OPT$ the size of the max independent set.
Let $S$ be the solution and $|S|$ is its size. We can write $X_i = 1$ if $v_{\sigma_i}$ vertex is added to $S$ and $0$ if not. Let $X$ be the number of vertices added to $S$.

Consider any vertex $v \in V$. If $v$ is not added to the independent set $S$, it must be because one of its neighbors was added to the independent set $S$ before it. The probability that $v$ is added to the independent set $S$ is at most $1/(d+1)$, it’s an upper bound. We calculate the expected value of the algorithm: we denote $u$ as an arbitrary vertex of $V$ and $N(v)$ the neighbors of $v$.

$$\mathbb{E}[X] = \mathbb{E}[X_1] + ... + \mathbb{E}[X_n]$$

\begin{align} \mathbb{E}[X_i] & = Pr[v_{\sigma_i} \text{ is added to }S | u \notin N(v_{\sigma_i})] \times Pr[u \notin N(v_{\sigma_i})]\\ & \qquad + Pr[v_{\sigma_i}\text{ is added to }S | u \in N(v_{\sigma_i})] \times Pr[u \in N(v_{\sigma_i})]\\ & = 1\times Pr[u \notin N(v_{\sigma_i})] + 0 \times Pr[u \in N(v_{\sigma_i})]\\ & = Pr[u \notin N(v_{\sigma_i})] \\ & = 1 - Pr[u \in N(v_{\sigma_i})] \end{align} since the maximum degree of a vertex is $d$, we have $Pr[u \notin N(v_{\sigma_i})] \leqslant $ (something? I'm not sure what) for all $i$ from $1$ to $n$.

Here I got stuck on how to proceed further. If there are mistakes in this I would be happy if you identify and correct.


1 Answer 1


Let $Y_v$ be the random variable that indicates whether vertex $v$ is added to the independence set. The probability that $v$ appears before all vertices that are incident to $v$ in a random ordering is $\frac1{\deg(v)+1}$, since all orderings are equally likely and all $\deg(v)+1$ vertices involved are symmetric to one another. On this situation $v$ will be added to the independence set. ($v$ can be added as well on other situations since none of its neighbors might have been added when $v$ appears after some of its neighbors.) We have $$E[Y_v]\ge\frac1{\deg(v)+1}\ge\frac1{d+1}.$$

So the expected value of $Y$, which is the size of the independence set returned by the given random algorithm is $$E[Y]=\sum_vE[Y_v]\ge\frac{|V|}{d+1}.$$

On the other hand, we will see that the size of the maximum independence set is at most $\frac {d|V|}{d+1}$. We can assume $G$ is connected since it is enough to prove for each connected component. We assume $d\ge1$; otherwise $d=0$, the situation is trivial while the proposition is ill-defined with $\frac1d$.

Let $M$ be a maximum independence set. Since each vertex in $M$ is incident to a vertex not in $M$ (otherwise that vertex is an isolated vertex, meaning $G$ is not connected), we have $$|M| \le|\text{vertices that are incident to }V\setminus M |.$$ Since each vertex is incident to at most $d$ vertices, we have $$|\text{vertices that are incident to }V\setminus M|\le d|V\setminus M|.$$ Since $|V\setminus M|=|V|-|M|$, we get $|M|\le d(|V|-|M|)$, i.e., $$|M|\le \frac {d|V|}{d+1}.$$

So $$\frac{E[Y]}{|M|}\ge\frac{\frac{|V|}{d+1}}{\frac {d|V|}{d+1}}\ge\frac1d,$$ which is what we are asked to prove.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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