On independent sets in random graphs |
| |
| Authors: | Amin Coja‐Oghlan Charilaos Efthymiou |
| |
| Affiliation: | Goethe University, Mathematics Institute, Frankfurt, Germany |
| |
| Abstract: | The independence number of a sparse random graph G(n,m) of average degree d = 2m/n is well‐known to be  with high probability, with  in the limit of large d. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size  , i.e., about half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with size  for any fixed  (independent of both d and n). 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  . Roughly speaking, we prove that independent sets of size  form an intricately rugged landscape, in which local search algorithms seem to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independent sets. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 436–486, 2015 |
| |
| Keywords: | random graphs independent set problem Metropolis process phase transitions |
|
|
