A sufficient condition to extend polynomial results for the Maximum Independent Set Problem

作者：Mosca Raffaele^*

来源：Discrete Applied Mathematics, 2017, 216: 281-289.

DOI：10.1016/j.dam.2015.10.023

• Maximum independent set problem
• Polynomial algorithms

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 is an element of 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 K-1 + F-free graphs (i.e., graphs which are K-1 + F-free for all F is an element of F) in polynomial time.
The main result of this paper is the following: A sufficient condition to extend the above proposition to K-2 + F-free graphs, and more generally to lK(2) + F-free graphs for any constant l (i.e., graphs which are lK(2) + F-free for all F is an element of 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 2K(2)-free graph has O(n(2)) maximal independent sets (Farber, 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 that idea/algorithm.

• 出版日期2017-1-10