- Journal Article
Rights / licenseIn Copyright - Non-Commercial Use Permitted
, expressing the simple condition that two adjacent nodes cannot belong to a stable set. We study the fractional stable set polytope, i.e. the polytope defined by the linear relaxation of the edge formulation. Even if this polytope is a weak approximation of the stable set polytope, its simple geometrical structure provides deep theoretical insight as well as interesting algorithmic opportunities. Exploiting a graphic characterization of the bases, we first redefine pivots in terms of simple graphic operations, that turn a given basis into an adjacent one. These results lead us to prove that the combinatorial diameter of the fractional stable set polytope is at most the number of nodes of the given graph. As a corollary, the Hirsch bound holds for this class of polytopes. Show more
Journal / seriesMathematical Programming
Pages / Article No.
SubjectPolytope; Diameter; Stable set problem
Organisational unit03873 - Weismantel, Robert / Weismantel, Robert
NotesIt was possible to publish this article open access thanks to a Swiss National Licence with the publisher.
MoreShow all metadata