A branch-and-cut for the stable set problem based on an ellipsoidal relaxation

A relevant amount of research has been focused on investigating strong relaxations for the stable set problem. In fact, polyhedral combinatorics techniques have been intensively developed since the early seventies in order to strengthen the natural linear formulation. Shortly afterwards, Lovasz introduced a celebrated semidefinite programming relaxation, known as theta relaxation. Later on, several attempts to strengthen it by adding linear inequalities have been investigated. The resulting upper bounds turn out to be very strong, but hardly accessible in practice. In this talk, we show that the Lovasz theta relaxation can be used to derive a new convex programming relaxation having the same optimal value. Moreover, the new relaxation has a more friendly structure, as its feasible region takes the form of an ellipsoid. We also investigate possible extension of this methodology to stronger relaxations.