G-2002-08
Stable Sets in Two Subclasses of Banner-Free Graphs
Michael U. Gerber, Alain Hertz et Vadim Lozin
The maximum stable set problem is NP-hard, even when restricted to banner-free graphs. In this paper, we use the augmenting graph approach to attack the problem in two subclasses of banner-free graphs. We first provide both classes with the complete characterization of minimal augmenting graphs. Based on the obtained characterization, we prove polynomial solvability of the problem in the class of (banner,P8)-free graphs, improving several existing results.
Paru en février 2002 , 20 pages