On the Lovász Theta function for independent sets in sparse graphs

N. Bansal, A. Gupta, G. Guruganesh

Research output: Contribution to journalArticleAcademic

62 Downloads (Pure)

Abstract

We consider the maximum independent set problem on graphs with maximum degree~$d$. We show that the integrality gap of the Lov\'asz $\vartheta$-function based SDP is $\widetilde{O}(d/\log^{3/2} d)$. This improves on the previous best result of $\widetilde{O}(d/\log d)$, and almost matches the integrality gap of $\widetilde{O}(d/\log^2 d)$ recently shown for stronger SDPs, namely those obtained using poly-$(\log(d))$ levels of the $SA^+$ semidefinite hierarchy. The improvement comes from an improved Ramsey-theoretic bound on the independence number of $K_r$-free graphs for large values of $r$. We also show how to obtain an algorithmic version of the above-mentioned $SA^+$-based integrality gap result, via a coloring algorithm of Johansson. The resulting approximation guarantee of $\widetilde{O}(d/\log^2 d)$ matches the best unique-games-based hardness result up to lower-order poly-$(\log\log d)$ factors.
Original languageEnglish
Article number1504.04767
Number of pages37
JournalarXiv.org, e-Print Archive, Physics
Publication statusPublished - 18 Apr 2015

Bibliographical note

Extended abstract to appear at the STOC 2015 conference

Fingerprint

Dive into the research topics of 'On the Lovász Theta function for independent sets in sparse graphs'. Together they form a unique fingerprint.

Cite this