The Library
Maximum independent sets in subcubic graphs : new results
Tools
Tools
Tools
Harutyunyan, A., Lampis, M., Lozin, Vadim V. and Monnot, J. (2020) Maximum independent sets in subcubic graphs : new results. Theoretical Computer Science, 846 . pp. 14-26. doi:10.1016/j.tcs.2020.09.010 ISSN 0304-3975.
|
PDF
WRAP-Maximum-independent-sets-subcubic-graphs-Lozin-2020.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (876Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.tcs.2020.09.010
Abstract
The maximum independent set problem is known to be NP-hard in the class of subcubic graphs, i.e. graphs of vertex degree at most 3. We study complexity of the problem on hereditary subclasses of subcubic graphs. Each such subclass can be described by means of forbidden induced subgraphs. In case of finitely many forbidden induced subgraphs a necessary condition for polynomial-time solvability of the problem in subcubic graphs (unless ) is the exclusion of the graph , which is a tree with three leaves of distance from the only vertex of degree 3. Whether this condition is also sufficient is an open question, which was previously answered only for -free subcubic graphs and -free subcubic graphs. Combining various algorithmic techniques, in the present paper we generalize both results and show that the problem can be solved in polynomial time for -free subcubic graphs, for any fixed value of k.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
| Library of Congress Subject Headings (LCSH): | Polynomials , Set theory | ||||||||
| Journal or Publication Title: | Theoretical Computer Science | ||||||||
| Publisher: | Elsevier Science BV | ||||||||
| ISSN: | 0304-3975 | ||||||||
| Official Date: | 18 December 2020 | ||||||||
| Dates: |
|
||||||||
| Volume: | 846 | ||||||||
| Page Range: | pp. 14-26 | ||||||||
| DOI: | 10.1016/j.tcs.2020.09.010 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 28 September 2020 | ||||||||
| Date of first compliant Open Access: | 11 September 2021 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
