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

Nikhil Bansal; Anupam Gupta; Guru Guruganesh

doi:10.1145/2746539.2746607

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

Nikhil Bansal, Anupam Gupta, Guru Guruganesh

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We consider the maximum independent set problem on sparse graphs with maximum degree d. We show that the integrality gap of the Lovász θ-function based SDP has an integrality gap of Õ(d/log^3/2d). This improves on the previous best result of Õ (d/log d), and narrows the gap of this basic SDP to the integrality gap of Õ(d/log² 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 Õ (d/log² d) matches the best unique-games-based hardness result up to lower-order poly (log log d) factors.

Original language	English (US)
Title of host publication	STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
Publisher	Association for Computing Machinery
Pages	193-200
Number of pages	8
ISBN (Electronic)	9781450335362
DOIs	https://doi.org/10.1145/2746539.2746607
State	Published - Jun 14 2015
Event	47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States Duration: Jun 14 2015 → Jun 17 2015

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
Volume	14-17-June-2015
ISSN (Print)	0737-8017

Other

Other	47th Annual ACM Symposium on Theory of Computing, STOC 2015
Country/Territory	United States
City	Portland
Period	6/14/15 → 6/17/15

ASJC Scopus subject areas

Software

Access to Document

10.1145/2746539.2746607

Cite this

Bansal, N., Gupta, A., & Guruganesh, G. (2015). On the Lovász Theta function for independent sets in sparse graphs. In STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing (pp. 193-200). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 14-17-June-2015). Association for Computing Machinery. https://doi.org/10.1145/2746539.2746607

On the Lovász Theta function for independent sets in sparse graphs. / Bansal, Nikhil; Gupta, Anupam; Guruganesh, Guru.
STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing. Association for Computing Machinery, 2015. p. 193-200 (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 14-17-June-2015).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bansal, N, Gupta, A & Guruganesh, G 2015, On the Lovász Theta function for independent sets in sparse graphs. in STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, vol. 14-17-June-2015, Association for Computing Machinery, pp. 193-200, 47th Annual ACM Symposium on Theory of Computing, STOC 2015, Portland, United States, 6/14/15. https://doi.org/10.1145/2746539.2746607

@inproceedings{34193f31307341af8dd296e34fbc4968,

title = "On the Lov{\'a}sz Theta function for independent sets in sparse graphs",

abstract = "We consider the maximum independent set problem on sparse graphs with maximum degree d. We show that the integrality gap of the Lov{\'a}sz θ-function based SDP has an integrality gap of {\~O}(d/log3/2d). This improves on the previous best result of {\~O} (d/log d), and narrows the gap of this basic SDP to the integrality gap of {\~O}(d/log2 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 Kr- 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 {\~O} (d/log2 d) matches the best unique-games-based hardness result up to lower-order poly (log log d) factors.",

author = "Nikhil Bansal and Anupam Gupta and Guru Guruganesh",

year = "2015",

month = jun,

day = "14",

doi = "10.1145/2746539.2746607",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "193--200",

booktitle = "STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing",

}

TY - GEN

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

AU - Bansal, Nikhil

AU - Gupta, Anupam

AU - Guruganesh, Guru

PY - 2015/6/14

Y1 - 2015/6/14

N2 - We consider the maximum independent set problem on sparse graphs with maximum degree d. We show that the integrality gap of the Lovász θ-function based SDP has an integrality gap of Õ(d/log3/2d). This improves on the previous best result of Õ (d/log d), and narrows the gap of this basic SDP to the integrality gap of Õ(d/log2 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 Kr- 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 Õ (d/log2 d) matches the best unique-games-based hardness result up to lower-order poly (log log d) factors.

AB - We consider the maximum independent set problem on sparse graphs with maximum degree d. We show that the integrality gap of the Lovász θ-function based SDP has an integrality gap of Õ(d/log3/2d). This improves on the previous best result of Õ (d/log d), and narrows the gap of this basic SDP to the integrality gap of Õ(d/log2 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 Kr- 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 Õ (d/log2 d) matches the best unique-games-based hardness result up to lower-order poly (log log d) factors.

UR - http://www.scopus.com/inward/record.url?scp=84958777909&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958777909&partnerID=8YFLogxK

U2 - 10.1145/2746539.2746607

DO - 10.1145/2746539.2746607

M3 - Conference contribution

AN - SCOPUS:84958777909

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 193

EP - 200

BT - STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 47th Annual ACM Symposium on Theory of Computing, STOC 2015

Y2 - 14 June 2015 through 17 June 2015

ER -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this