The stable set problem: some structural properties and relaxations
- PDF / 73,930 Bytes
- 2 Pages / 439.37 x 666.142 pts Page_size
- 106 Downloads / 194 Views
The stable set problem: some structural properties and relaxations Carla Michini
Published online: 17 November 2012 © Springer-Verlag Berlin Heidelberg 2012
This is a summary of the author’s PhD thesis supervised by Antonio Sassano and defended on June 4, 2012 at Sapienza Università di Roma. The thesis is written in English and is available at http://padis.uniroma1.it/bitstream/10805/1598/1/ thesisCarlaMichini.pdf. The thesis deals with a polyhedral study of the fractional stable set polytope and aims mainly at establishing some new structural properties of this polytope. The fractional stable set polytope is the polytope defined by the linear relaxation of the edge formulation of the stable set problem. The edge formulation is defined by two-variable constraints, one for each edge of a graph G, expressing the simple condition that two adjacent nodes cannot belong to a stable set. Even if the fractional stable set 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 simplex pivots in terms of simple graphic operations, that turn a given basis into an adjacent one. Among all possible pivots, we characterize degenerate and non-degenerate ones, and we differentiate those leading to an integer or to a fractional vertex. The graphic characterization of bases is crucial to prove another structural property of the fractional stable set polytope, concerning the adjacency of its vertices. In particular, we extend a necessary and sufficient condition due to Chvátal for adjacency of (integer) vertices of the stable set polytope to arbitrary (and possibly fractional) vertices of the fractional stable set polytope. These results lead us to prove that the Hirsch conjecture is true for the fractional stable set polytope, i.e. the combinatorial diameter of this fractional polytope is at most equal to the number of edges of the given graph. We actually refine
C. Michini (B) IFOR, ETH Zürich, Rämistrasse 101, 8092 Zürich, Switzerland e-mail: [email protected]
123
200
C. Michini
this bound in the nonbipartite case by proving a tighter bound, equal to the number of nodes of the graph. We also design a simplex-like algorithm for the stable set problem that relies on the adjacency properties mentioned above. Our algorithm generates only integer solutions without using cutting plane methods. Preliminary results are encouraging but show that cycling can occur, due to the high degree of degeneracy of the polytope. Nevertheless, the perspective of an exact combinatorial method of solution for the stable set problem based on this algorithm seems promising, provided that an anti-cycling rule is embedded in its current design. The graphic characterization of bases also provides a significant assessment on strength of different corner relaxations for the edge formulation of the maximum cardinality stable set problem. The corner relax
Data Loading...
