New Results on Independent Sets in Extensions of 2K(2)-free Graphs

The Maximum Weight Independent Set Problem (WIS) is a well-known NP-hard problem. A popular way to study WIS is to detect graph classes for which WIS is solvable in polynomial time, with particular reference to hereditary graph classes, i.e., defined by a hereditary graph property or equivalently by forbidding one or more induced subgraphs. For any two graphs G and H, G + H denotes the disjoint union of G and H. A lK(2) is the disjoint union of l edges. A Y-m,Y-m is the disjoint union of two stars of m + 1 vertices plus one vertex that is adjacent only to the centers of such stars. For any graph family Y, the class of Y-free graphs is formed by graphs which are Y-free for every Y is an element of Y, and the class of lK(2) + Y-free graphs is formed by graph which are lK(2) + Y-free for every Y is an element of Y. The main result of this manuscript is the following: For any constant m and for any graph family Y which contains an induced subgraph of Y-m,Y-m, if WIS is solvable in polynomial time for Y-free graphs, then WIS is solvable in polynomial time for lK(2) + Y-free graphs for any constant l. That extends some known polynomial results, namely, when Y = {Y} and Y is a fork or is a P-5. The proof of the main result is based on Farber's approach to prove that every 2K(2)-free graph has O(n(2)) maximal independent sets (Farber in Discrete Math 73:249-260, 1989), which directly leads to a polynomial time algorithm to solve WIS for 2K(2)-free graphs through a dynamic programming approach, and on some extensions of Farber's approach.