main page — CS 627 Advanced Algorithms
Unit 5: Parameterized Hardness
This unit covers
- fpt-reductions
- para-NP-hardness
- W[1]-hardness
Material
- slides
- Video 5-1 (2025-05-27):
Parameterized reductions
- Video 5-2 (2025-05-27):
para-NP
- Video 5-3 (2025-05-28):
Bounded nondeterminism & W[P]
- Video 5-4 (2025-05-28):
Tail-nondeterminism & W[1]
- Video 5-5 (2025-06-03):
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