An SDP primal-dual algorithm for approximating the lovász-theta function

Abstract

The Lovász v-function [Lov79] on a graph G = (V, E) can be defined as the maximum of the sum of the entries of a positive semidefinite matrix X, whose trace Tr(X) equals 1, and X i j = 0 whenever {i, j} ε E. This function appears as a subroutine for many algorithms for graph problems such as maximum independent set and maximum clique. We apply Arora and Kale's primal-dual method for SDP to design an approximate algorithm for the v-function with an additive error of δ > 0, which runs in time O(α2n2/δ 2 logn - Me), where α = v(G) and Me = O(n3) is the time for a matrix exponentiation operation. Moreover, our techniques generalize to the weighted Lovász v-function, and both the maximum independent set weight and the maximum clique weight for vertex weighted perfect graphs can be approximated within a factor of (1+ε) in time O(ε -2n 5 log n). © 2009 IEEE.