Formulations for the stable set polytope
F. Bruce Shepherd, William R. Pulleyblank · London School of Economics and Political Science Research Online (London School of Economics and Political Science) · 1992
We give a simple algorithm for the weighted stable set problem of an arbitrary graph which yields an extended formulation for its stable set polytope 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 The extended formulation we obtain is of polynomial size for distance claw free graphs These graphs are of interest from the point of view of their stable set polyhedra due to the fact that all of the complicated necessary inequalities given by Giles and Trotter for the polyhedra of claw free graphs are also necessary for the class of distance claw free graphs