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,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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alexe, G., Hammer, P.L., Lozin, V.V., de Werra, D.: Struction revisited. Discrete Appl. Math. 132(1–3), 27–46 (2003)
Bodlaender, H.L., Thilikos, D.M.: Treewidth for graphs with small chordality. Discrete Appl. Math. 79(1–3), 45–61 (1997)
Brandstädt, A., Lozin, V.V., Mosca, R.: Independent sets of maximum weight in apple-free graphs. SIAM J. Discrete Math. 24(1), 239–254 (2010)
Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1(2), 180–187 (1972)
Lozin, V.V.: From matchings to independent sets. Discrete Appl. Math. 231, 4–14 (2017)
Lozin, V.V., Milanic, M.: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. J. Discrete Algorithms 6(4), 595–604 (2008)
Lozin, V.V., Milanic, M., Purcell, C.: Graphs without large apples and the maximum weight independent set problem. Graphs Combinatorics 30(2), 395–410 (2014)
Lozin, V.V., Monnot, J., Ries, B.: On the maximum independent set problem in subclasses of subcubic graphs. J. Discrete Algorithms 31, 104–112 (2015)
Minty, G.J.: Minty on maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Ser. B 28(3), 284–304 (1980)
Murphy, O.J.: Computing independent sets in graphs with large girth. Discrete Appl. Math. 35(2), 167–170 (1992)
Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55(2), 221–232 (1985)
Whitesides, S.: An algorithm for finding clique cut-sets. Inf. Process. Lett. 12(1), 31–32 (1981)
Acknowledgment
Vadim Lozin acknowledges support from the Russian Science Foundation Grant No. 17-11-01336.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Harutyunyan, A., Lampis, M., Lozin, V., Monnot, J. (2019). Maximum Independent Sets in Subcubic Graphs: New Results. In: Sau, I., Thilikos, D. (eds) Graph-Theoretic Concepts in Computer Science. WG 2019. Lecture Notes in Computer Science(), vol 11789. Springer, Cham. https://doi.org/10.1007/978-3-030-30786-8_4
Download citation
DOI: https://doi.org/10.1007/978-3-030-30786-8_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-30785-1
Online ISBN: 978-3-030-30786-8
eBook Packages: Computer ScienceComputer Science (R0)