Tightness of lp via max-product belief propagation

We investigate the question of tightness of linear programming (LP) relaxation for finding a maximum weight independent set (MWIS) in sparse random weighted graphs. We show that an edge-based LP relaxation is asymptotically tight for Erdos-Renyi graph G(n,c/n) for c≤2e and random regular graph G(n,r) for r≤4 when node weights are i.i.d. with exponential distribution of mean 1. We establish these results, through a precise relation between the tightness of LP relaxation and convergence of the max-product belief propagation algorithm. We believe that this novel method of understanding structural properties of combinatorial problems through properties of iterative procedure such as the max-product should be of interest in its own right.