ECCC-Report TR05-050https://eccc.weizmann.ac.il/report/2005/050Comments and Revisions published for TR05-050en-usThu, 02 Jun 2005 00:00:00 +0300
Revision 1
| Finding a Maximum Independent Set in a Sparse Random Graph Revision of: TR05-050 |
Uriel Feige,
Eran Ofek
https://eccc.weizmann.ac.il/report/2005/050#revision1We 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$.
Thu, 02 Jun 2005 00:00:00 +0300https://eccc.weizmann.ac.il/report/2005/050#revision1
Paper TR05-050
| Finding a Maximum Independent Set in a Sparse Random Graph |
Uriel Feige,
Eran Ofek
https://eccc.weizmann.ac.il/report/2005/050We 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$.
Tue, 26 Apr 2005 02:54:27 +0300https://eccc.weizmann.ac.il/report/2005/050