Martin, B. and Paulusma, D. and Smith, S. (2022) 'Hard problems that quickly become very easy.', Information Processing Letters, 174 . p. 106213.
Abstract
A graph class is hereditary if it is closed under vertex deletion. We give examples of NP-hard, PSPACE-complete and NEXPTIME-complete problems that become constant-time solvable for every hereditary graph class that is not equal to the class of all graphs.
| Item Type: | Article |
|---|---|
| Full text: | Publisher-imposed embargo until 15 October 2022. (AM) Accepted Manuscript Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0. File format - PDF (387Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.1016/j.ipl.2021.106213 |
| Publisher statement: | © 2021 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ |
| Date accepted: | 13 October 2021 |
| Date deposited: | 25 October 2021 |
| Date of first online publication: | 15 October 2021 |
| Date first made open access: | 15 October 2022 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
