2005/08/23 by Sujay Sanghavi, Devavrat Shah, Sanghavi, Sujay +1
Computer Science · #Bayesian Modeling and Causal Inference #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Theory and Algorithms #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0508097
openalex publication_date 2005/08/23 · arxiv created 2008/04/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.