Optimization Online


The stable set problem and the lift-and-project ranks of graphs

Laszlo Liptak (lliptak***at***math.uwaterloo.ca)
Levent Tuncel (ltuncel***at***math.uwaterloo.ca)

Abstract: We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lov\'asz and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures' performances change as we apply fundamental graph operations. We show that the odd subdivision of an edge and the subdivision of a star operations (as well as their common generalization, the stretching of a vertex operation) cannot decrease the $N_0$-, $N$-, or $N_+$-rank of the graph. We also provide graph classes (which contain the complete graphs) where these operations do not increase the $N_0$- or the $N$-rank. Hence we obtain the ranks for these graphs, and we also present some graph-minor like characterizations for them. Despite these properties we give examples showing that in general most of these operations can increase these ranks. Finally, we provide improved bounds for $N_+$-ranks of graphs in terms of the number of nodes in the graph and prove that the subdivision of an edge or cloning a vertex can increase the $N_+$-rank of a graph.

Keywords: stable set problem, lift-and-project, semidefinite lifting, semidefinite programming, integer programming

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: CORR 2002-13, Dept. of Combinatorics and Optimization, University of Waterloo, Ontario, CANADA, May 2002 (revised: December 2002).

Download: [Postscript]

Entry Submitted: 12/20/2002
Entry Accepted: 12/22/2002
Entry Last Modified: 12/20/2002

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