Stable set

Terminology

A stable set is the same as an independent set: a set $S\subseteq V$ such that no edge has both endpoints in $S$.

Randomized algorithm

Let $G=(V,E)$.

1. Keep each vertex independently with probability $p$.
2. Let $V_p$ be the set of kept vertices and start with $S_0=V_p$.
3. For each edge $e=\{u,v\}$ with both $u,v\in S_0$, remove one of its endpoints from $S_0$.
4. Let $S$ be the remaining set.

Then $S$ is a stable set.

NOTE

A simpler variant removes both endpoints of every surviving edge. That also produces a stable set, but it gives the weaker bound $|S|\ge X-2Y$ instead of $|S|\ge X-Y$.

Expectation analysis

Let $G=(V,E)$ with $|V|=n$ and $|E|=m$.

For each vertex $v\in V$, let $X_v$ be the indicator variable that $v$ is kept:

$$X_v=\{\begin{array}{ll}1,& v\in V_p,\\ 0,& \text{otherwise.}\end{array}$$

Then $\mathbb{E}[X_v]=p$, so for $X={\sum }_{v\in V}{X}_v$ we get

$$\mathbb{E}[X]=np.$$

For each edge $e=\{u,v\}\in E$, let $Y_e$ be the indicator variable that both endpoints survive the first round. Then

$$\mathbb{E}[Y_e]=p^2$$

because the two vertex choices are independent. Hence for $Y={\sum }_{e\in E}{Y}_e$ we get

$$\mathbb{E}[Y]=m{p}^2.$$

Each surviving edge forces at most one deletion, hence

$$|S|\ge X-Y.$$

Taking expectations gives (using linearity of expectation)

$$\mathbb{E}[|S|]\ge \mathbb{E}[X-Y]=\mathbb{E}[X]-\mathbb{E}[Y]=np-m{p}^2.$$

Optimal choice of $p$

To maximize the lower bound

$$f(p)=np-m{p}^2,$$

differentiate:

$$f^{\prime }(p)=n-2mp.$$

So the stationary point is

$$p=\frac{n}{2m}.$$

If this value lies in $[0,1]$, it is the optimal choice, and then

$$\mathbb{E}[|S|]\ge n\cdot \frac{n}{2m}-m{\left(\frac{n}{2m}\right)}^2=\frac{n^2}{4m}.$$