Parameterized problems complete for nondeterministic FPT time and logarithmic space ☆

Hans L. Bodlaender; Carla Groenland; Jesper Nederlof; Celine Swennenhuis

doi:10.1016/j.ic.2024.105195

Parameterized problems complete for nondeterministic FPT time and logarithmic space ☆

Hans L. Bodlaender, Carla Groenland, Jesper Nederlof, Celine Swennenhuis

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

Abstract

Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time f(k)n^O(1) and space f(k)log⁡(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as LIST COLORING and PRECOLORING EXTENSION with pathwidth as parameter, SCHEDULING OF JOBS WITH PRECEDENCE CONSTRAINTS, with both number of machines and partial order width as parameter, BANDWIDTH and variants of WEIGHTED CNF-SATISFIABILITY. In particular, this implies that all these problems are W[t]-hard for all t.

Original language	English
Article number	105195
Number of pages	34
Journal	Information and Computation
Volume	300
DOIs	https://doi.org/10.1016/j.ic.2024.105195
Publication status	Published - Oct 2024

Bibliographical note

Publisher Copyright:
© 2024 The Author(s)

Funding

The work of Jesper Nederlof was supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 853234).The work of C\u00E9line Swennenhuis was supported by the Netherlands Organisation for Scientific Research under project no. 613.009.031b.

Funders	Funder number
European Research Council
European Union's Horizon 2020 Research and Innovation Programme	853234
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	613.009.031b.

Keywords

Bandwidth minimization
Dynamic-programming algorithms
Graphs
Pathwidth
Tractability

Access to Document

10.1016/j.ic.2024.105195Licence: CC BY

1-s2.0-S0890540124000609-mainFinal published version, 992 KBLicence: CC BY

Cite this

@article{90a4ffbd27aa4b41a8a8f3ac8fe9dd99,

title = "Parameterized problems complete for nondeterministic FPT time and logarithmic space ☆",

abstract = "Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time f(k)nO(1) and space f(k)log⁡(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as LIST COLORING and PRECOLORING EXTENSION with pathwidth as parameter, SCHEDULING OF JOBS WITH PRECEDENCE CONSTRAINTS, with both number of machines and partial order width as parameter, BANDWIDTH and variants of WEIGHTED CNF-SATISFIABILITY. In particular, this implies that all these problems are W[t]-hard for all t.",

keywords = "Bandwidth minimization, Dynamic-programming algorithms, Graphs, Pathwidth, Tractability",

author = "Bodlaender, {Hans L.} and Carla Groenland and Jesper Nederlof and Celine Swennenhuis",

note = "Publisher Copyright: {\textcopyright} 2024 The Author(s)",

year = "2024",

month = oct,

doi = "10.1016/j.ic.2024.105195",

language = "English",

volume = "300",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Parameterized problems complete for nondeterministic FPT time and logarithmic space ☆

AU - Bodlaender, Hans L.

AU - Groenland, Carla

AU - Nederlof, Jesper

AU - Swennenhuis, Celine

PY - 2024/10

Y1 - 2024/10

N2 - Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time f(k)nO(1) and space f(k)log⁡(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as LIST COLORING and PRECOLORING EXTENSION with pathwidth as parameter, SCHEDULING OF JOBS WITH PRECEDENCE CONSTRAINTS, with both number of machines and partial order width as parameter, BANDWIDTH and variants of WEIGHTED CNF-SATISFIABILITY. In particular, this implies that all these problems are W[t]-hard for all t.

AB - Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time f(k)nO(1) and space f(k)log⁡(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as LIST COLORING and PRECOLORING EXTENSION with pathwidth as parameter, SCHEDULING OF JOBS WITH PRECEDENCE CONSTRAINTS, with both number of machines and partial order width as parameter, BANDWIDTH and variants of WEIGHTED CNF-SATISFIABILITY. In particular, this implies that all these problems are W[t]-hard for all t.

KW - Bandwidth minimization

KW - Dynamic-programming algorithms

KW - Graphs

KW - Pathwidth

KW - Tractability

UR - http://www.scopus.com/inward/record.url?scp=85199857167&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2024.105195

DO - 10.1016/j.ic.2024.105195

M3 - Article

SN - 0890-5401

VL - 300

JO - Information and Computation

JF - Information and Computation

M1 - 105195

ER -

Parameterized problems complete for nondeterministic FPT time and logarithmic space ☆

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this