We study certain linear and semidefinite programming lifting approximation schemes for computing the stability number of a graph. Our work is based on, and refines De Klerk and Pasechnik’s approach to approximating the stability number via copositive programming (SIAM J. Optim. 12 (2002), 875–892). We provide a closed-form expression for the values computed by the linear programming approximations. We also show that the exact value of the stability number $\alpha(G)$ is attained by the semidefinite approximation of order $\alpha(G)-1$ as long as $\alpha(G) \leq 6$. Our results reveal some sharp differences between the linear and the semidefinite approximations. For instance, the value of the linear programming approximation of any order is strictly larger than $\alpha(G)$ whenever $\alpha(G) > 1$.
Citation
SIAM Journal on Optimization 18 (2007) pp. 87--105.