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