Groupe d’études et de recherche en analyse des décisions

G-91-36

New Polynomially Solvable Cases for the Maximum Stable Set Problem

We describe two new classes of graphs for which the stability number can be computed in polynomial time. The first approach is based on an iterative procedure which, at each step, builds from a graph G a new graph G' which has fewer vertices and has the property that (G') = (G) - 1. For the second class, it can be decided in polynomial time whether there exists a stable set of given size k. These new classes of graphs are different from the known classes for which the stability number can be computed in polynomial time.

, 20 pages