Hard problems that quickly become very easy

Barnaby Martin; Daniël Paulusma; Siani Smith

doi:10.1016/j.ipl.2021.106213

Hard problems that quickly become very easy

Barnaby Martin
, Daniël Paulusma^*
, Siani Smith

^*Corresponding author for this work

School of Mathematics

Research output: Contribution to journal › Article (Academic Journal) › peer-review

5 Citations (Scopus)

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.

Original language	English
Article number	106213
Number of pages	6
Journal	Information Processing Letters
Volume	174
Early online date	15 Oct 2021
DOIs	https://doi.org/10.1016/j.ipl.2021.106213
Publication status	Published - 1 Mar 2022

Bibliographical note

Funding Information:
Supported by the Leverhulme Trust (RPG-2016-258).

Publisher Copyright:
© 2021 Elsevier B.V.

Keywords

Computational complexity
H-free
Hereditary graph class

Access to Document

10.1016/j.ipl.2021.106213

Handle.net

Persistent link

Cite this

@article{7458666d545746f28080e1fd91714601,

title = "Hard problems that quickly become very easy",

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.",

keywords = "Computational complexity, H-free, Hereditary graph class",

author = "Barnaby Martin and Dani{\"e}l Paulusma and Siani Smith",

note = "Funding Information: Supported by the Leverhulme Trust (RPG-2016-258). Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2022",

month = mar,

day = "1",

doi = "10.1016/j.ipl.2021.106213",

language = "English",

volume = "174",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Hard problems that quickly become very easy

AU - Martin, Barnaby

AU - Paulusma, Daniël

AU - Smith, Siani

PY - 2022/3/1

Y1 - 2022/3/1

N2 - 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.

AB - 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.

KW - Computational complexity

KW - H-free

KW - Hereditary graph class

UR - https://www.scopus.com/pages/publications/85119949395

U2 - 10.1016/j.ipl.2021.106213

DO - 10.1016/j.ipl.2021.106213

M3 - Article (Academic Journal)

AN - SCOPUS:85119949395

SN - 0020-0190

VL - 174

JO - Information Processing Letters

JF - Information Processing Letters

M1 - 106213

ER -

Hard problems that quickly become very easy

Abstract

Bibliographical note

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this