Maximum weight independent set for lclaw-free graphs in polynomial time

For a finite, simple, undirected graph G with a vertex weight function, the Maximum Weight Independent Set (MWIS) problem asks for an independent vertex set of G with maximum weight. MWIS is a well-known NP-hard problem of fundamental importance. For claw-free graphs, MWIS can be solved in polynomial time—in 1980, the first two such algorithms were independently found by Minty for MWIS and by Sbihi for the unweighted case. For a constant ℓ≥2, let ℓG denote the disjoint union of ℓ copies of G. In this paper, using a dynamic programming approach (inspired by Farber's result about MWIS for 2K2-free graphs), we show that for any fixed ℓ MWIS can be solved in polynomial time for ℓclaw-free graphs. This solves the open cases for MWIS on (P3+ claw)-free graphs and on (2K2+claw)-free graphs and extends known results for claw-free graphs, ℓK2-free graphs, (K2+claw)-free graphs, and ℓP3-free graphs. © 2017 Elsevier B.V.