Date
2019
Dewey
Recherche opérationnelle
Sujet
Independent set; Sub-Cubic graphs; Apple-Free graphs
Conference name
Graph-Theoretic Concepts in Computer Science, 45th International Workshop, WG 2019
Conference date
2019
Author
Ignasi Sau, Dimitrios M. Thilikos
Publisher
Springer International Publishing
Publisher city
Berlin Heidelberg
ISBN
978-3-030-30785-1;978-3-030-30786-8
Author
Harutyunyan, Ararat
Lampis, Michael
Lozin, Vadim
Monnot, Jérôme
Type
Communication / Conférence
Item number of pages
40-52
Abstract (EN)
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 Sk,k,k, for some k. Here, Sk,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 Sk,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 S2,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.