Stable Sets

In this chapter we show a general compact extended formulation for the relaxation of the stable set polytope. For some graphs the stable set polytope can be given an exact representation, although with an exponential number of inequalities. When the graphs are perfect, however, compact extended formulations are possible for the stable set polytope. We give an example of such situation by describing a compact extended formulation, obtained by LP techniques, for the class of comparability graphs