01-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.
Preprint series: 01-24, Preprints
- MSC:
- 90C10 Integer programming
- 90C27 Combinatorial optimization
- 05C60 Isomorphism problems (reconstruction conjecture, perfect graphs, etc.)
- 05C70 Factorization, matching, 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
Notes: 1st, 2nd, 3rd and 5th author supported by the European DONET program TMR ERB FMRX-CT98-0202. 2nd, 3rd and 5th author supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. 5th author supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft.
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.