We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Hard problems that quickly become very easy

Martin, B. and Paulusma, D. and Smith, S. (2022) 'Hard problems that quickly become very easy.', Information Processing Letters, 174 . p. 106213.


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
Publisher Web site:
Publisher statement:© 2021 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
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

Look up in GoogleScholar