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

N. Bansal; Anupam Gupta; G. Guruganesh

doi:10.1145/2746539.2746607

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

N. Bansal, Anupam Gupta, G. Guruganesh

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

9 Citations (Scopus)

4 Downloads (Pure)

Abstract

We consider the maximum independent set problem on graphs with maximum degree d. We show that the integrality gap of the Lovasz Theta function-based SDP has an integrality gap of O~(d/log3/2 d). 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 SAplus-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.

Original language	English
Title of host publication	47th Annual ACM Symposium on the Theory of Computing (STOC'15, Portland OR, USA, June 14-17, 2015)
Editors	R.A. Servedio, R. Rubinfeld
Place of Publication	New York NY
Publisher	Association for Computing Machinery, Inc
Pages	193-200
ISBN (Print)	978-1-4503-3536-2
DOIs	https://doi.org/10.1145/2746539.2746607
Publication status	Published - 2015
Event	47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA - Portland, OR, United States Duration: 14 Jun 2015 → 17 Jun 2015 http://acm-stoc.org/stoc2015/

Conference

Conference	47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA
Abbreviated title	STOC 2015
Country/Territory	United States
City	Portland, OR
Period	14/06/15 → 17/06/15
Internet address	http://acm-stoc.org/stoc2015/

Access to Document

10.1145/2746539.2746607

Cite this

@inproceedings{fa76ff0db9ec4e0b8809a5f0a7cadaeb,

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

abstract = "We consider the maximum independent set problem on graphs with maximum degree d. We show that the integrality gap of the Lovasz Theta function-based SDP has an integrality gap of O~(d/log3/2 d). 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 SAplus-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 = "N. Bansal and Anupam Gupta and G. Guruganesh",

year = "2015",

doi = "10.1145/2746539.2746607",

language = "English",

isbn = "978-1-4503-3536-2",

pages = "193--200",

editor = "R.A. Servedio and R. Rubinfeld",

booktitle = "47th Annual ACM Symposium on the Theory of Computing (STOC'15, Portland OR, USA, June 14-17, 2015)",

publisher = "Association for Computing Machinery, Inc",

address = "United States",

note = "47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA, STOC 2015 ; Conference date: 14-06-2015 Through 17-06-2015",

url = "http://acm-stoc.org/stoc2015/",

}

Bansal, N, Gupta, A & Guruganesh, G 2015, On the Lovász theta function for independent sets in sparse graphs. in RA Servedio & R Rubinfeld (eds), 47th Annual ACM Symposium on the Theory of Computing (STOC'15, Portland OR, USA, June 14-17, 2015). Association for Computing Machinery, Inc, New York NY, pp. 193-200, 47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA, Portland, OR, United States, 14/06/15. https://doi.org/10.1145/2746539.2746607

On the Lovász theta function for independent sets in sparse graphs. / Bansal, N.; Gupta, Anupam; Guruganesh, G.
47th Annual ACM Symposium on the Theory of Computing (STOC'15, Portland OR, USA, June 14-17, 2015). ed. / R.A. Servedio; R. Rubinfeld. New York NY: Association for Computing Machinery, Inc, 2015. p. 193-200.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Bansal, N.

AU - Gupta, Anupam

AU - Guruganesh, G.

PY - 2015

Y1 - 2015

N2 - We consider the maximum independent set problem on graphs with maximum degree d. We show that the integrality gap of the Lovasz Theta function-based SDP has an integrality gap of O~(d/log3/2 d). 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 SAplus-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.

AB - We consider the maximum independent set problem on graphs with maximum degree d. We show that the integrality gap of the Lovasz Theta function-based SDP has an integrality gap of O~(d/log3/2 d). 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 SAplus-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.

U2 - 10.1145/2746539.2746607

DO - 10.1145/2746539.2746607

M3 - Conference contribution

SN - 978-1-4503-3536-2

SP - 193

EP - 200

BT - 47th Annual ACM Symposium on the Theory of Computing (STOC'15, Portland OR, USA, June 14-17, 2015)

A2 - Servedio, R.A.

A2 - Rubinfeld, R.

PB - Association for Computing Machinery, Inc

CY - New York NY

T2 - 47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA

Y2 - 14 June 2015 through 17 June 2015

ER -

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

Abstract

Conference

Access to Document

Fingerprint

Cite this