Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
Javier Peña, Juan C. Vera, Luis F. Zuluaga · SIAM Journal on Optimization · 2007
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), pp. 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$.