Formulations for the stable set polytope of a claw-free graph Extended abstract

We give a conceptually simple algorithm for the weighted stable set problem which yields a higher dimensional formulation for the stable set polytope of a graph. The algorithm runs in polynomial time for the class of distance claw-free graphs. These are the graphs such that for each node, neither its neighbour set nor the set of nodes at distance two contain a stable set of size three. In addition, the resulting higher dimensional formulation for distance claw-free graphs is compact. The distance claw-free graphs are of interest with respect to stable set polyhedra due to the fact that all of the complicated necessary inequalities given by Giles and Trotter for the class of claw-free graphs are also necessary for the class of distance claw-free graphs. This together with the fact that distance claw-free graphs exhibit much stronger structural properties, suggests the class to be a natural candidate to consider in future workAvailable from TIB Hannover: RN 4052(93796) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman