TY - JOUR

T1 - Approximating the independence number via the θ-function

AU - Alon, Noga

AU - Kahale, Nabil

N1 - Funding Information:
* Corresponding author. Email: [email protected]. Research supported in part by a USA-Israel BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences and by the Minkowski Minerva Center for Geometry at Tel Aviv University. ‘This work was partly done while the author was at XEROX PARC and partly at DIMACS. Email: [email protected] 0025-5610/98/$19.00 @ 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V. PI1 SOO25-5610(97)00028-2

PY - 1998/2/1

Y1 - 1998/2/1

N2 - We describe an approximation algorithm for the independence number of a graph. If a graph on n vertices has an independence number n/k+m for some fixed integer k ≥ 3 and some m > 0, the algorithm finds, in random polynomial time, an independent set of size Ω̃(m3/(k+1)), improving the best known previous algorithm of Boppana and Halldorsson that finds an independent set of size Ω(m1/(k-1)) in such a graph. The algorithm is based on semi-definite programming, some properties of the Lovász θ-function of a graph and the recent algorithm of Karger, Motwani and Sudan for approximating the chromatic number of a graph. If the θ-function of an n vertex graph is at least Mn1-2/k for some absolute constant M, we describe another, related, efficient algorithm that finds an independent set of size k. Several examples show the limitations of the approach and the analysis together with some related arguments supply new results on the problem of estimating the largest possible ratio between the θ-function and the independence number of a graph on n vertices.

AB - We describe an approximation algorithm for the independence number of a graph. If a graph on n vertices has an independence number n/k+m for some fixed integer k ≥ 3 and some m > 0, the algorithm finds, in random polynomial time, an independent set of size Ω̃(m3/(k+1)), improving the best known previous algorithm of Boppana and Halldorsson that finds an independent set of size Ω(m1/(k-1)) in such a graph. The algorithm is based on semi-definite programming, some properties of the Lovász θ-function of a graph and the recent algorithm of Karger, Motwani and Sudan for approximating the chromatic number of a graph. If the θ-function of an n vertex graph is at least Mn1-2/k for some absolute constant M, we describe another, related, efficient algorithm that finds an independent set of size k. Several examples show the limitations of the approach and the analysis together with some related arguments supply new results on the problem of estimating the largest possible ratio between the θ-function and the independence number of a graph on n vertices.

KW - Approximation algorithms

KW - Independence number of a graph

KW - Semi-definite programming

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

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

U2 - 10.1007/BF01581168

DO - 10.1007/BF01581168

M3 - Article

AN - SCOPUS:0001262835

SN - 0025-5610

VL - 80

SP - 253

EP - 264

JO - Mathematical Programming, Series B

JF - Mathematical Programming, Series B

IS - 3

ER -