Maximum independent sets in subcubic graphs: New results.

The maximum independent set problem is known to be NP-hard in the class of subcubic graphs, i.e. graphs of vertex degree at most 3. We study complexity of the problem on hereditary subclasses of subcubic graphs. Each such subclass can be described by means of forbidden induced subgraphs. In case of finitely many forbidden induced subgraphs a necessary condition for polynomial-time solvability of the problem in subcubic graphs (unless P = N P) is the exclusion of the graph S i , j , k , which is a tree with three leaves of distance i , j , k from the only vertex of degree 3. Whether this condition is also sufficient is an open question, which was previously answered only for S 1 , k , k -free subcubic graphs and S 2 , 2 , 2 -free subcubic graphs. Combining various algorithmic techniques, in the present paper we generalize both results and show that the problem can be solved in polynomial time for S 2 , k , k -free subcubic graphs, for any fixed value of k. [ABSTRACT FROM AUTHOR]