Maximum Independent Sets in Subcubic Graphs: New Results

International audienceWe 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 subcu-bic 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 S2,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