Optimization Online


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

Javier Pena (jfp***at***andrew.cmu.edu)
Juan Vera (jvera***at***andrew.cmu.edu)
Luis Zuluaga (lzuluaga***at***unb.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.


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society