Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
482195 | European Journal of Operational Research | 2008 | 11 Pages |
The maximum weight stable set problem (MWS) is the weighted version of the maximum stable set problem (MS), which is NP-hard. The class of P5-free graphs – i.e., graphs with no induced path of five vertices – is the unique minimal class, defined by forbidding a single connected subgraph, for which the computational complexity of MS is an open question. At the same time, it is known that MS can be efficiently solved for (P5,F)(P5,F)-free graphs, where F is any graph of five vertices different to a C5. In this paper we introduce some observations on P5-free graphs, and apply them to introduce certain subclasses of such graphs for which one can efficiently solve MWS. That extends or improves some known results, and implies – together with other known results – that MWS can be efficiently solved for (P5,F)(P5,F)-free graphs where F is any graph of five vertices different to a C5.