ON THE LOVASZ THETA FUNCTION FOR INDEPENDENT SETS IN SPARSE GRAPHS

被引:10
作者
Bansal, Nikhil [1 ,2 ]
Gupta, Anupam [3 ]
Guruganesh, Guru [3 ]
机构
[1] Eindhoven Univ Technol, NL-5600 MB Eindhoven, Netherlands
[2] CWI, NL-1098 XG Amsterdam, Netherlands
[3] Carnegie Mellon Univ, Comp Sci Dept, Pittsburgh, PA 15213 USA
关键词
algorithms; Ramsey theory; semidefinite programmming; NUMBER; HYPERGRAPHS; APPROXIMATE; ALGORITHMS; CLIQUE;
D O I
10.1137/15M1051002
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider the maximum independent set problem on sparse graphs with maximum degree d. We show that the Lovasz V-function based semidefinite program (SDP) has an integrality gap of (O) over tilde (d/log(3/2) d), improving on the previous best result of (O) over tilde (d/log d). This improvement is based on a new Ramsey-theoretic bound on the independence number of K-r-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) over tilde (d/log(2) 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.
引用
收藏
页码:1039 / 1055
页数:17
相关论文
共 35 条
[1]   ON TURAN THEOREM FOR SPARSE GRAPHS [J].
AJTAI, M ;
ERDOS, P ;
KOMLOS, J ;
SZEMEREDI, E .
COMBINATORICA, 1981, 1 (04) :313-317
[2]   A NOTE ON RAMSEY NUMBERS [J].
AJTAI, M ;
KOMLOS, J ;
SZEMEREDI, E .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1980, 29 (03) :354-360
[3]   Approximating the independence number via the θ-function [J].
Alon, N ;
Kahale, N .
MATHEMATICAL PROGRAMMING, 1998, 80 (03) :253-264
[4]   Coloring graphs with sparse neighborhoods [J].
Alon, N ;
Krivelevich, M ;
Sudakov, B .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1999, 77 (01) :73-82
[5]  
Alon N, 1996, RANDOM STRUCT ALGOR, V9, P271, DOI 10.1002/(SICI)1098-2418(199610)9:3<271::AID-RSA1>3.0.CO
[6]  
2-U
[7]  
Alon N., 1992, The probabilistic method
[8]  
Austrin P., 2011, THEORY COMPUTING, V7, P27, DOI [DOI 10.4086/TOC.2011.V007A003, DOI 10.4086/T0C.2011.V007A003]
[9]   The early evolution of the H-free process [J].
Bohman, Tom ;
Keevash, Peter .
INVENTIONES MATHEMATICAE, 2010, 181 (02) :291-336
[10]  
Chan SO, 2013, STOC'13: PROCEEDINGS OF THE 2013 ACM SYMPOSIUM ON THEORY OF COMPUTING, P447