On independent sets in random graphs

Authors


  • Supported by EPSRC grant (EP/G039070/2); DIMAP. A preliminary version of this work appeares in the proceedings of ACM-SIAM SODA 2011.

Abstract

The independence number of a sparse random graph G(n,m) of average degree d = 2m/n is well-known to be inline image with high probability, with inline image in the limit of large d. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size inline image, 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 inline image for any fixed inline image (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 inline image. Roughly speaking, we prove that independent sets of size inline image 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

Ancillary