On the Lovász Theta function for Independent Sets in Sparse Graphs

Nikhil Bansal, Anupam Gupta, Guru Guruganesh

We consider the maximum independent set problem on graphs with maximum degree~$d$. We show that the integrality gap of the Lovász $\vartheta$-function based SDP is $\widetilde{O}(d…