__
Revision #1 to TR05-050 | 2nd June 2005 00:00
__
#### Finding a Maximum Independent Set in a Sparse Random Graph Revision of: TR05-050

**Abstract:**
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$.

__
TR05-050 | 18th April 2005 00:00
__

#### Finding a Maximum Independent Set in a Sparse Random Graph

**Abstract:**
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$.