Parameterized Problems Complete for Nondeterministic FPT Time and Logarithmic Space

Explore a 29-minute lecture on parameterized problems complete for nondeterministic FPT time and logarithmic space. Delve into the class XNLP, which encompasses parameterized problems solvable nondeterministically in f(k)n^O(1) time and f(k) log(n) space. Discover a wide array of XNLP-complete problems, including List Coloring, Precoloring Extension with pathwidth parameter, Scheduling of Jobs with Precedence Constraints, Bandwidth, and variants of Weighted CNF-Satisfiability and reconfiguration problems. Learn about the implications of these findings, such as the W[t]-hardness for all t and the resolution of a long-standing question on the parameterized complexity of the Bandwidth problem. Gain insights from the collaborative work of Hans Bodlaender, Carla Groenland, Jesper Nederlof, and Céline Swennenhuis at the Hausdorff Center for Mathematics.

Hans Bodlaender: Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space