Computing the stability number of a graph via linear and semidefinite programming

Javier Pena (jfpandrew.cmu.edu)
Juan Vera (jveraandrew.cmu.edu)
Luis Zuluaga (lzuluagaunb.ca)

Abstract: 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$.

Keywords: stability number, copositivity, polynomials, lifting procedures

Category 1: Combinatorial Optimization (Other )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: SIAM Journal on Optimization 18 (2007) pp. 87--105.

Download:

Entry Submitted: 04/08/2005
Entry Accepted: 04/08/2005
Entry Last Modified: 06/27/2007

Modify/Update this entry