We consider the complexity of the classical independent Set problem on classes of subcubic graphs characterized by a finite set of forbidden induced subgraphs. It is well-known that a necessary condition for Independent Set to be tractable in such a class (unless P = NP) is that the set of forbidden induced subgraphs includes a subdivided star S_(k,k,k), for some k. Here, S_(k,k,k) is the graph obtained by taking three paths of length k and identifying one of their endpoints. It is an interesting open question whether this condition is also sufficient: is Independent Set tractable on all hereditary classes of subcubic graphs that exclude some S_(k,k,k)? A positive answer to this question would provide a complete classification of the complexity of Independent Set on all classes of subcubic graphs characterized by a finite set of forbidden induced subgraphs. The best currently known result of this type is tractability for S_(2,2,2)-free graphs. In this paper we generalize this result by showing that the problem remains tractable on S_(2,k,k)-free graphs, for any fixed k. Along the way, we show that subcubic Independent Set is tractable for graphs excluding a type of graph we call an "apple with a long stem", generalizing known results for apple-free graphs.
展开▼
