Maximum Independent Sets in Subcubic Graphs: New Results
Harutyunyan, Ararat; Lampis, Michael; Lozin, Vadim; Monnot, Jérôme (2019), Maximum Independent Sets in Subcubic Graphs: New Results, Graph-Theoretic Concepts in Computer Science, 45th International Workshop, WG 2019, 2019
TypeCommunication / Conférence
Conference titleGraph-Theoretic Concepts in Computer Science, 45th International Workshop, WG 2019
Book authorIgnasi Sau, Dimitrios M. Thilikos
MetadataShow full item record
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.
Subjects / KeywordsIndependent set; Sub-Cubic graphs; Apple-Free graphs
Showing items related by title and author.
Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019) Communication / Conférence