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.
Discovery Building, Orchard View Room