Hard problems that quickly become very easy

Martin, B.; Paulusma, D.; Smith, S.

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.

• Journal Article Type: Article
• Acceptance Date: Oct 13, 2021
• Online Publication Date: Oct 15, 2021
• Publication Date: 2022-03
• Deposit Date: Oct 23, 2021
• Publicly Available Date: Oct 15, 2022
• Journal: Information Processing Letters
• Print ISSN: 0020-0190
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 174
• DOI: https://doi.org/10.1016/j.ipl.2021.106213
• Public URL: https://durham-repository.worktribe.com/output/1228725