WHEEL INEQUALITIES FOR STABLE SET POLYTOPES

We introduce new classes of valid inequalities, called wheel inequalit ies, for the stable set polytope P-G of a graph G. Each ''wheel config uration'' gives rise to two such inequalities. The simplest wheel conf iguration is an ''odd'' subdivision W of a wheel, and for these we giv e necessary and sufficient conditions for the wheel inequality to be f acet-inducing for P-W. Generalizations arise by allowing subdivision p aths to intersect, and by replacing the ''hub'' of the wheel by a cliq ue. The separation problem for these inequalities can be solved in pol ynomial time. (C) 1997 The Mathematical Programming Society, Inc.