2018
On the Lovász theta function for independent sets in sparse graphs
Publication
Publication
SIAM Journal on Computing , Volume 47 - Issue 3 p. 1039- 1055
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.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.1137/15M1051002 | |
| SIAM Journal on Computing | |
| Organisation | 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 |
|
