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 · transcript (2026-11-09, 11:05): Parameterized Reductions
- Video 5-2 · transcript (2026-11-09, 9:39): Nondeterministic FPT - para-NP
- Video 5-3 · transcript (2026-11-09, 26:56): Bounded Nondeterminism - W[P]
- Video 5-3 · transcript (2026-11-09, 22:38): Tail-Nondeterminism - W[1]
- Video 5-4 · transcript (2026-11-12, 40:01): p-IndependentSet is W[1]-complete
- Video 5-4 · transcript (2026-11-12, 14:34): W[1]-hardness reductions
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