Abstract :

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. In 1982, Alekseev showed that the M(W)IS problem remains NP-complete on H-free graphs, whenever H is connected, but neither a path nor a subdivision of the claw. In this talk, we will focus on H-free graphs, where H is a path nor a subdivision of the claw, and show that the MWIS problem can be solved in polynomial time in certain classes of these graphs.