An extended formulation for the 1‐wheel inequalities of the stable set polytope.

The 1‐wheel inequalities for the stable set polytope were introduced by Cheng and Cunningham. In general, there is an exponential number of these inequalities. We present a new polynomial size extended formulation of the stable set relaxation that includes the odd cycle and 1‐wheel inequalities. This compact formulation allows one to polynomially optimize over a polyhedron instead of handling the separation problem for 1‐wheel inequalities by solving many shortest walk problems and relying on the ellipsoid method. [ABSTRACT FROM AUTHOR]