Polyhedral results on the stable set problem and on half-integral polytopes

In many optimization problems the set of feasible solutions can be described or approximated through a polyhedron. In this talk, I will focus on the polyhedral structure of specific classes of polytopes.

First, I will introduce the fractional stable set polytope, that arises from the edge formulation of the stable set problem and is half-integral. I will present a graphic characterization of vertices and vertex adjacency for this polytope, and I will describe how to use this knowledge for algorithmic purposes, showing that the diameter of the polytope cannot exceed the number of nodes of the input graph.

Then, I will present some more general results concerning the diameter of lattice polytopes, i.e. polytopes whose vertices are integral. I will show a new bound on the diameter of these polytopes and an algorithm to find a path between two given vertices, whose length does not exceed the bound. These results imply that the diameter of a n-dimensional half-integral polytope is at most 3/2 n, and I will show that this bound is tight.