We consider the problem of finding a maximum independent set in a
random graph. The random graph $G$ is modelled 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 algorithms 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{\frac{c_0
}{d}}$, where $c_0$ is some sufficiently large constant
independent of $d$.

We consider the problem of finding a maximum independent set in a
random graph. The random graph $G$ is modelled 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 algorithms 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{\frac{c_0 \log d}{d}}$, where $c_0$ is
some sufficiently large constant independent of $d$.