On independent sets in random graphs

Abstract

The independence number of a sparse random graph G(n,m) of average degree d=2m/n is well-known to be α(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.

Polished previous version

References in corpus (7)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The hard-core model on random graphs revisited
• Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time
• Maximum independent sets on random regular graphs
• Limits of local-global convergent graph sequences
• Phase transitions for the cavity approach to the clique problem on random graphs
• Reconstruction Threshold for the Hardcore Model

Cited by in corpus (21)

• Local algorithms for independent sets are half-optimal
• Information-theoretic thresholds for community detection in sparse networks
• Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
• Quantum independent set problem and non-abelian adiabatic mixing
• Quantum Algorithm for Approximating Maximum Independent Sets
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• Message Passing Variational Autoregressive Network for Solving Intractable Ising Models
• Spin glass phase transitions in the random feedback vertex set problem
• Generalized random sequential adsorption on Erdős-Rényi random graphs
• An algorithmic framework for colouring locally sparse graphs
• Online learning with feedback graphs and switching costs
• Group testing and local search: is there a computational-statistical gap?
• Independent Sets of Random Trees and of Sparse Random Graphs
• Algebraic dynamical systems from LDPC codes satisfy a strong negation of the weak Pinsker property
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Note on induced paths in sparse random graphs
• On the replica symmetry phase of the independent set problem
• Counting independent sets in percolated graphs via the Ising model
• Large independent sets in recursive Markov random graphs
• Sum-of-Squares Lower Bounds for Sparse Independent Set