Abstract
It is known that the maximum independent set problem is NP-complete for subcubic graphs, i.e. graphs of vertex degree at most 3. Moreover, the problem is NP-complete for H-free subcubic graphs whenever H contains a connected component which is not a tree with at most 3 leaves. We show that if every connected component of H is a tree with at most 3 leaves and at most 7 vertices, then the problem can be solved for H-free subcubic graphs in polynomial time.
The first author gratefully acknowledges support from DIMAP - the Center for Discrete Mathematics and its Applications at the University of Warwick, and from EPSRC, grant EP/I01795X/1.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Alekseev, V.E.: On the local restrictions effect on the complexity of finding the graph independence number. In: Combinatorial-Algebraic Methods in Applied Mathematics, pp. 3–13. Gorkiy University Press (1983) (in Russian)
Bodlaender, H.L., Thilikos, D.M.: Treewidth for graphs with small chordality. Discrete Appl. Math. 79, 45–61 (1997)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guie to the Theory of NP-Completeness, 5th edn. W.H. Freeman (1979) ISBN 0-7167-1045-5
Gerber, M.U., Hertz, A., Schindl, D.: P 5-free augmenting graphs and the maximum stable set problem. Discrete Applied Mathematics 132, 109–119 (2004)
Lozin, V., Milanič, M.: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. J. Discrete Algorithms 6, 595–604 (2008)
Lozin, V.V., Milanic, M., Purcell, C.: Graphs Without Large Apples and the Maximum Weight Independent Set Problem. Graphs and Combinatorics, doi:10.1007/s00373-012-1263-y
Lozin, V.V., Mosca, R.: Maximum regular induced subgraphs in 2P 3-free graphs. Theoret. Comput. Sci. 460, 26–33 (2012)
Lozin, V.V., Mosca, R.: Maximum independent sets in subclasses of P 5-free graphs. Information Processing Letters 109, 319–324 (2009)
Maffray, F.: Stable sets in k-colorable P 5-free graphs. Information Processing Letters 109, 1235–1237 (2009)
Mosca, R.: Some results on maximum stable sets in certain P 5-free graphs. Discrete Applied Mathematics 132, 175–183 (2003)
Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Combin. Theory Ser. B 28, 284–304 (1980)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lozin, V., Monnot, J., Ries, B. (2013). On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs. In: Lecroq, T., Mouchard, L. (eds) Combinatorial Algorithms. IWOCA 2013. Lecture Notes in Computer Science, vol 8288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45278-9_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-45278-9_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45277-2
Online ISBN: 978-3-642-45278-9
eBook Packages: Computer ScienceComputer Science (R0)