Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR05-050 | 2nd June 2005 00:00

#### Finding a Maximum Independent Set in a Sparse Random Graph Revision of: TR05-050

Revision #1
Authors: Uriel Feige, Eran Ofek
Accepted on: 2nd June 2005 00:00
Keywords:

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$.

### Paper:

TR05-050 | 18th April 2005 00:00

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

TR05-050
Authors: Uriel Feige, Eran Ofek
Publication: 26th April 2005 02:54
Keywords:

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$.

ISSN 1433-8092 | Imprint