POLYNOMIAL ALGORITHMS FOR THE MAXIMUM STABLE SET PROBLEM ON PARTICULAR CLASSES OF P-5-FREE GRAPHS

The Maximum Stable Set Problem (MS) is a well-known NP-hard problem. A popular research stream considers classes of graphs, defined in terms of forbidden subgraphs, in which either MS is NP-hard or can be solve d by polynomial algorithms. In this paper we focus on three of these c lasses: in one of them, MS is still NP-hard; in the others, the proble m difficulty is an open question. However, for those graphs in such cl asses that have no induced paths with five vertices (P-5), the problem becomes solvable in polynomial time. Whether MS is difficult or not i n the class of P-5-free graphs is still open. (C) 1997 Elsevier Scienc e B.V.