Paper Info
Title
Maximum Independent Sets In Subcubic Graphs: New Results
Abstract
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,S- k,S-k, for some k. Here, S-k,S- k,S-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,S- k,S-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,S-2,S-2-free graphs. In this paper we generalize this result by showing that the problem remains tractable on S-2,S- k,S-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.
Year
DOI
Venue
2018
10.1007/978-3-030-30786-8_4
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2019)
Keywords
Field
DocType
Independent set, Sub-Cubic graphs, Apple-Free graphs
Discrete mathematics,Graph,Combinatorics,Subclass,Generalization,Independent set,Degree (graph theory),Mathematics
Journal
Volume
ISSN
Citations 
11789
0302-9743
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Ararat Harutyunyan15213.08
Michael Lampis210422.13
Vadim V. Lozin394783.65
Jérôme Monnot451255.74