Parameterized problems complete for nondeterministic FPT time and logarithmic space
Hans L. Bodlaender (Universiteit Utrecht)
Carla Groenland (TU Delft - Discrete Mathematics and Optimization)
Jesper Nederlof (Universiteit Utrecht)
C.M.F. Swennenhuis (TU Delft - Electrical Engineering, Mathematics and Computer Science, Eindhoven University of Technology)
More Info
expand_more
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.
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.
help_outline