Approximating the independence number via the θ-function

Noga Alon, Nabil Kahale

Research output: Contribution to journalArticle

80 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)253-264
Number of pages12
JournalMathematical Programming, Series B
Volume80
Issue number3
DOIs
StatePublished - Feb 1 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Approximation algorithms
  • Independence number of a graph
  • Semi-definite programming

Fingerprint Dive into the research topics of 'Approximating the independence number via the θ-function'. Together they form a unique fingerprint.

  • Cite this