An SDP Primal-Dual Algorithm for Approximating the Lovasz-Theta Function
The Lovasz Theta function 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} is in E.
This function appears as a subroutine for many algorithms on graph
problems such as maximum independent set and maximum clique. We
apply Arora and Kale's primal-dual method for SDP to design an
algorithm to approximate the Theta-function within an additive error
of d > 0 which runs in time O( (an/d)^2 (log n) M_e), where a =
Theta(G) and M_e = O(n^3) is the time for a matrix exponentiation
operation. It follows that on perfect graphs G, our primal-dual
method computes Theta(G) exactly in time O(a^2 n^5 log n).
Moreover, our techniques generalize to the weighted Lovasz
Theta-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 + e) in time $O( n^5/e^2 log n)$.
This is joint work with Kevin Chang and Rajiv Raman.