Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space

Hans L. Bodlaender; Carla Groenland; Jesper Nederlof; Céline M.F. Swennenhuis

doi:10.1109/FOCS52979.2021.00027

Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space

Hans L. Bodlaender
, Carla Groenland
, Jesper Nederlof
, Céline M.F. Swennenhuis

Combinatorial Optimization

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

26 Citations (Scopus)

Abstract

Let XNLP be the class of parameterized prob-lems 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 Coloringand Precoloring Extensionwith pathwidth as parameter, Scheduling Of Jobs With Precedence Constraints, with both number of machines and partial order width as parameter, Bandwidthand variants of Weighted Cnf-satisfiability and reconfiguration problems. In particular, this implies that all these problems are W[t]-hard for all t. This also answers a long standing question on the parameterized complexity of the Bandwidth problem.

Original language	English
Title of host publication	2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021
Publisher	Institute of Electrical and Electronics Engineers
Pages	193-204
Number of pages	12
ISBN (Electronic)	978-1-6654-2055-6
DOIs	https://doi.org/10.1109/FOCS52979.2021.00027
Publication status	Published - 4 Mar 2022
Event	62nd Annual Symposium on Foundations of Computer Science, FOCS 2021 - Virtual Duration: 7 Feb 2022 → 10 Feb 2022

Conference

Conference	62nd Annual Symposium on Foundations of Computer Science, FOCS 2021
Abbreviated title	FOCS 2021
City	Virtual
Period	7/02/22 → 10/02/22

Keywords

Bandwidth
Parameterized complexity
Whierarchy
XNLP

Access to Document

10.1109/FOCS52979.2021.00027

pdfFinal published version, 599 KBLicence: TAVERNE

Cite this

Bodlaender, H. L., Groenland, C., Nederlof, J., & Swennenhuis, C. M. F. (2022). Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021 (pp. 193-204). Article 9719711 Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/FOCS52979.2021.00027

@inproceedings{2b502c20f0d54484b76a6a0b357b0c95,

title = "Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space",

abstract = "Let XNLP be the class of parameterized prob-lems 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 Coloringand Precoloring Extensionwith pathwidth as parameter, Scheduling Of Jobs With Precedence Constraints, with both number of machines and partial order width as parameter, Bandwidthand variants of Weighted Cnf-satisfiability and reconfiguration problems. In particular, this implies that all these problems are W[t]-hard for all t. This also answers a long standing question on the parameterized complexity of the Bandwidth problem.",

keywords = "Bandwidth, Parameterized complexity, Whierarchy, XNLP",

author = "Bodlaender, \{Hans L.\} and Carla Groenland and Jesper Nederlof and Swennenhuis, \{C{\'e}line M.F.\}",

year = "2022",

month = mar,

day = "4",

doi = "10.1109/FOCS52979.2021.00027",

language = "English",

pages = "193--204",

booktitle = "2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

note = "62nd Annual Symposium on Foundations of Computer Science, FOCS 2021, FOCS 2021 ; Conference date: 07-02-2022 Through 10-02-2022",

}

Bodlaender, HL, Groenland, C, Nederlof, J & Swennenhuis, CMF 2022, Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space. in 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021., 9719711, Institute of Electrical and Electronics Engineers, pp. 193-204, 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021, Virtual, 7/02/22. https://doi.org/10.1109/FOCS52979.2021.00027

Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space. / Bodlaender, Hans L.; Groenland, Carla; Nederlof, Jesper et al.
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021. Institute of Electrical and Electronics Engineers, 2022. p. 193-204 9719711.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space

AU - Bodlaender, Hans L.

AU - Groenland, Carla

AU - Nederlof, Jesper

AU - Swennenhuis, Céline M.F.

PY - 2022/3/4

Y1 - 2022/3/4

N2 - Let XNLP be the class of parameterized prob-lems 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 Coloringand Precoloring Extensionwith pathwidth as parameter, Scheduling Of Jobs With Precedence Constraints, with both number of machines and partial order width as parameter, Bandwidthand variants of Weighted Cnf-satisfiability and reconfiguration problems. In particular, this implies that all these problems are W[t]-hard for all t. This also answers a long standing question on the parameterized complexity of the Bandwidth problem.

AB - Let XNLP be the class of parameterized prob-lems 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 Coloringand Precoloring Extensionwith pathwidth as parameter, Scheduling Of Jobs With Precedence Constraints, with both number of machines and partial order width as parameter, Bandwidthand variants of Weighted Cnf-satisfiability and reconfiguration problems. In particular, this implies that all these problems are W[t]-hard for all t. This also answers a long standing question on the parameterized complexity of the Bandwidth problem.

KW - Bandwidth

KW - Parameterized complexity

KW - Whierarchy

KW - XNLP

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

U2 - 10.1109/FOCS52979.2021.00027

DO - 10.1109/FOCS52979.2021.00027

M3 - Conference contribution

SP - 193

EP - 204

BT - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021

PB - Institute of Electrical and Electronics Engineers

T2 - 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021

Y2 - 7 February 2022 through 10 February 2022

ER -

Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this