Nikhil Bansal: Approximating maximum independent set in sparse graphs

We consider the maximum independent set problem on graphs with maximum degree d. The best known result for the problem is an SDP based O(d log log d/ log d) approximation. It is also known that no \(o(d/log^2d)\) approximation exists assuming the Unique Games Conjecture.

We will describe several new results for this problem.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 show how to make this result algorithmic using d levels of the hierarcy. Finally, we give improved bounds on the intergrality gap of the standard SDP formulation. A key ingredient here is a new Ramsey theoretic result about the existence of non-trivial independent sets in graphs without large cliques.

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 the nibble methods.