Zurück zu den Preprints des Jahres 2001


On the Way to Perfection: A New Combinatorial Algorithm for Stable Sets in Graphs

by Gentile, C., Haus, U.-U., Köppe, M., Rinaldi, G., Weismantel, R..

Series: 2001-24, Preprints

90C10 Integer programming
90C27 Combinatorial optimization
05C60 Isomorphism problems (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C70 Factorization, matching, partitioning, covering and packing

In this paper some operations are described that transform every graph
into a perfect graph by replacing nodes with sets of new nodes. The
transformation is done in such a way that every stable set in the perfect
graph corresponds to a stable set in the original graph. These
operations yield a purely combinatorial augmentation procedure for
finding a maximum weighted stable set in a graph. Starting with a
stable set in a given graph one defines a simplex type tableau whose
associated basic feasible solution is the incidence vector of the
stable set. In an iterative fashion, non-basic columns that would
lead to pivoting into non-integral basic feasible solutions, are
replaced by new columns that one can read off from special graph
structures such as odd holes, odd antiholes, and various
generalizations. Eventually, either a pivot leading to an integral
basic feasible solution is performed, or the optimality of the current
solution is proved.

stable sets, primal integer programming, integral basis methods