Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949902 | Discrete Applied Mathematics | 2017 | 9 Pages |
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 can be solved in polynomial time, with particular reference to hereditary graph classes (i.e., defined by a hereditary graph property), or equivalently to F-free graphs for a given graph family F (i.e., graphs which are F-free for all FâF).A tool to extend the results which show that for given hereditary graph classes the WIS problem can be solved in polynomial time is given by the following easy proposition: For any graph family F, if WIS can be solved for F-free graphs in polynomial time, then WIS can be solved for K1+F-free graphs (i.e., graphs which are K1+F-free for all FâF) in polynomial time.The main result of this paper is the following: A sufficient condition to extend the above proposition to K2+F-free graphs, and more generally to lK2+F-free graphs for any constant l (i.e., graphs which are lK2+F-free for all FâF), is that F-free graphs are m-plausible for a constant m, i.e., that for any F-free graph G the family of those maximal independent sets I of G such that every vertex of G not in I has more than m neighbors in I can be computed in polynomial time. In this context a section is devoted to show that (for instance) chordal graphs are m-plausible for a constant m.The proof of the main result is based on the idea/algorithm introduced by Farber to prove that every 2K2-free graph has O(n2) maximal independent sets (Farber, 1989), which directly leads to a polynomial time algorithm to solve WIS for 2K2-free graphs through a dynamic programming approach, and on some extensions of that idea/algorithm.