On independent sets in random graphs

Details On independent sets in random graphs On independent sets in random graphs

2010-07-08

arxiv.org/abs/1007.1378v2

Computer Science

Discrete Mathematics

Scientific paper

The independence number of a sparse random graph G(n,m) of average degree d=2m/n is well-known to be \alpha(G(n,m))~2n ln(d)/d with high probability. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size (1+o(1)) n ln(d)/d, i.e. half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with (1+c)n ln(d)/d, for any fixed c>0. In this paper we prove that the combinatorial structure of the independent set problem in random graphs undergoes a phase transition as the size k of the independent sets passes the point k~nln(d)/d. Roughly speaking, we prove that independent sets of size k>(1+c)n ln(d)/d form an intricately ragged landscape, in which local search algorithms are bound to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independents sets.

Affiliated with

Also associated with

No associations

Rating

On independent sets in random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On independent sets in random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On independent sets in random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-103058