An SDP Primal-Dual Algorithm for Approximating the Lovász-Theta Function

The Lovász ϑ‐function (Lovász in IEEE Trans. Inf. Theory, 25:1–7, 1979) of 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 ij =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 algorithm to approximate the ϑ‐function within an additive error of δ>0, which runs in time $O(\frac{{\vartheta }^2{n}^2}{{\delta }^2}\log n\cdot M_e)$ , where ϑ=ϑ(G) and M e =O(n ³) is the time for a matrix exponentiation operation. It follows that for perfect graphs G, our primal‐dual method computes ϑ(G) exactly in time O(ϑ ² n ⁵logn). Moreover, our techniques generalize to the weighted Lovász ϑ‐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(ϵ ⁻² n ⁵logn).