Finding a Maximum Independent Set in a Sparse Random Graph

We consider the problem of finding a maximum independent set in a random graph. The random graph $G$, which contains $n$ vertices, is modeled as follows. Every edge is included independently with probability $\frac{d}{n}$, where $d$ is some sufficiently large constant. Thereafter, for some constant $\alpha$, a subset $I$ of $\alpha n$ vertices is chosen at random, and all edges within this subset are removed. In this model, the planted independent set $I$ is a good approximation for the maximum independent set $I_{max}$, but both $I \setminus I_{max}$ and $I_{max} \setminus I$ are likely to be nonempty. We present a polynomial time algorithm that with high probability (over the random choice of random graph $G$ and without being given the planted independent set $I$) finds the maximum independent set in $G$ when $\alpha \geq \sqrt{c_0 /d}$, where $c_0$ is some sufficiently large constant independent of $d$.