On independent sets in random graphs†
- †
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 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