Zurück zu den Preprints des Jahres 2001


2001-24

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

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

Abstract:
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.

Keywords:
stable sets, primal integer programming, integral basis methods