Hard problems that quickly become very easy

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

doi:10.1016/j.ipl.2021.106213

Hard problems that quickly become very easy

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

Authors

Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

Siani Alice Smith siani.smith@durham.ac.uk
PGR Student Doctor of Philosophy

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.

Citation

Martin, B., Paulusma, D., & Smith, S. (2022). Hard problems that quickly become very easy. Information Processing Letters, 174, https://doi.org/10.1016/j.ipl.2021.106213

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

Files

Accepted Journal Article (395 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/

Copyright 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/