Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space

Conference paper (2022)

Authors

Hans L. Bodlaender Universiteit Utrecht
C.E. Groenland Universiteit Utrecht
Jesper Nederlof Universiteit Utrecht
Celine M.F. Swennenhuis Eindhoven University of Technology
Affiliation
External organisation
Bandwidth Parameterized complexity Whierarchy XNLP
More Info
expand_more

Published Date

2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

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.