On the lovász theta function for independent sets in sparse graphs

Nikhil Bansal, Anupam Gupta, Guru Guruganesh

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1039-1055
Number of pages17
JournalSIAM Journal on Computing
Volume47
Issue number3
DOIs
StatePublished - 2018

Keywords

  • Algorithms
  • Ramsey theory
  • Semidefinite programmming

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics

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