Approximating Maximum Independent Set in Sparse Graphs

We consider the independent set problem on graphs with maximum degree d. It is known that no o(d/ log^2 d) approximation is possible assuming the Unique Games Conjecture. We show almost matching upper bounds based on some old and new Ramsey theoretic results. In particular, we show that the natural LP formulation for the problem strengthened by poly-logarithmic levels of the Shearli-Adams(+) hierarcy has an integrality gap of about O(d/log^2d).  We also give an algorithmic version using d levels of the hierarchy, and show improved bounds on the integrality gap of the standard Lovasz Theta SDP. The talk will give a broad overview of the techniques and the concepts involved, such as LP/SDP hiearchies, and Ramsey theoretic techniques such as Shearer's entropy based approach and nibble methods.

Based on joint work with Anupam Gupta and Guru Guruganesh.