APPROXIMATING THE INDEPENDENCE NUMBER VIA THE THETA-FUNCTION

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 greater than or equal to 3 and some m > 0, the a lgorithm finds, in random polynomial time, an independent set of size <(Omega)over tilde> (m(3/(k+1))), improving the best known previous al gorithm of Boppana and Halldorsson that finds an independent set of si ze Omega (m(1/(k-1))) in such a graph. The algorithm is based on semi- definite programming, some properties of the Lovasz v-function of a gr aph and the recent algorithm of Karger, Motwani and Sudan for approxim ating the chromatic number of a graph. If the v-function of an n verte x 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 t he problem of estimating the largest possible ratio between the v-func tion and the independence number of a graph on n vertices. (C) 1998 Th e Mathematical Programming Society, Inc. Published by Elsevier Science B.V.