main page — CS 627 Advanced Algorithms
Unit 5: Parameterized Hardness
This is an archived version of this module from Summer 2025.
Click here for the current iteration.
This unit covers
- fpt-reductions
- para-NP-hardness
- W[1]-hardness
Material
- slides
- Video 5-1 (2025-05-27, 16:34):
Parameterized reductions
- Video 5-2 (2025-05-27, 18:07):
para-NP
- Video 5-3 (2025-05-28, 38:47):
Bounded nondeterminism & W[P]
- Video 5-4 (2025-05-28, 41:47):
Tail-nondeterminism & W[1]
- Video 5-5 (2025-06-03, 8:22):
Recap & W[1]-hardness
Further reading and sources
Many examples are taken from Advanced Algorithms, following the module in Kaiserslautern initially developed by Markus Nebel.
Further reading:
- Flum, Grohe (2006): Parameterized Complexity Theory
- M. Cygan et al. (2015): Parameterized Algorithms