We consider the maximum independent set problem on sparse graphs with maximum degree d. We show that the Lovász ϑ-function based semidefinite program (SDP) has an integrality gap of O(d/log3/2 d), improving on the previous best result of O(d/log d). This improvement is based on a new Ramsey-theoretic bound on the independence number of Kr-free graphs for large values of r. We also show that for stronger SDPs, namely, those obtained using polylog(d) levels of the SA+ semidefinite hierarchy, the integrality gap reduces to O(d/log2 d). This matches the best unique-games-based hardness result up to lower-order poly(log log d) factors. Finally, we give an algorithmic version of this SA+-based integrality gap result, albeit using d levels of SA+, via a coloring algorithm of Johansson.

, ,
SIAM Journal on Computing
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Bansal, N., Gupta, A., & Guruganesh, G. (2018). On the Lovász theta function for independent sets in sparse graphs. SIAM Journal on Computing, 47(3), 1039–1055. doi:10.1137/15M1051002