The Hirsch Conjecture for the fractional stable set polytope
OPEN ACCESS
Author / Producer
Date
2014-10
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
, 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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
147 (1-2)
Pages / Article No.
309 - 330
Publisher
Springer
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Polytope; Diameter; Stable set problem
Organisational unit
03873 - Weismantel, Robert / Weismantel, Robert
Notes
It was possible to publish this article open access thanks to a Swiss National Licence with the publisher.