Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space.

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

Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space.

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

Research output: Contribution to journal › Article › Academic

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 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
Journal	CoRR
Volume	abs/2105.14882
Publication status	Published - 2021

Bibliographical note

DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

Access to Document

Cite this

@article{b2fe503c7c2a44d88823777fa1c0a6af,

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

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

note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

year = "2021",

language = "English",

volume = "abs/2105.14882",

journal = "CoRR",

issn = "2331-8422",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

}

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, Céline M. F.

N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2021

Y1 - 2021

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 spacef(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 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 problems such that an instance of size n with parameter k can be solved nondeterministically in time f(k)nO(1) and spacef(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 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.

M3 - Article

SN - 2331-8422

VL - abs/2105.14882

JO - CoRR

JF - CoRR

ER -

Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space.

Abstract

Bibliographical note

Access to Document

Fingerprint

Cite this