On the maximum independent set problem in subclasses of subcubic graphs
BP2-STS
- Lozin, Vadim Warwick University, United Kingdom
- Monnot, Jérôme Université Paris Dauphine-PSL, France
- Ries, Bernard ORCID Université Paris Dauphine-PSL, France
- 2014
Published in:
- Journal of Discrete Algorithms. - Elsevier BV. - 2014, vol. 31, p. 104-112
Computational Theory and Mathematics
Discrete Mathematics and Combinatorics
Theoretical Computer Science
Independent set
Polynomial-time algorithm
Subcubic graph
APX-completeness
English
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 3-regular Hamiltonian graphs and 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 His 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. We also strengthen the NP-completeness of the problem on 3-regular Hamiltonian graphs by showing that the problem is APX-complete in this class.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- Rights reserved
- Open access status
- bronze
- Identifiers
-
- DOI 10.1016/j.jda.2014.08.005
- ISSN 1570-8667
- Persistent URL
- https://folia.unifr.ch/unifr/documents/322639
Statistics
Document views: 34
File downloads:
- independentset.pdf: 77