main page — CS 627 Advanced Algorithms
Unit 4: Fixed-Parameter Algorithms
This unit covers
- Fixed-parameter tractability
- Depth-bounded search trees
- Kernelization
- Linear recurrences
Material
- slides
- Video 4-1 · transcript (2026-10-26, 15:21):
Parameterized Problems
- Video 4-2 · transcript (2026-10-29, 23:57):
Fixed Parameter Tractability
- Video 4-3 · transcript (2026-10-29, 16:21):
Depth-Bounded Search I
- Video 4-4 · transcript (2026-10-29, 39:44):
Kernelization
- Video 4-5 · transcript (2026-11-02, 9:58):
Kernel for p-MaxSat
- Video 4-6 · transcript (2026-11-02, 38:56):
Depth-Bounded Search for Planar Independent Set
- Video 4-7 · transcript (2026-11-02, 15:17):
Depth-Bounded Search for Closest String
Further reading and sources
Many examples are taken from Advanced Algorithms, following the module in Kaiserslautern initially developed by Markus Nebel.
Further reading:
- M. Cygan et al. (2015): Parameterized Algorithms
The techniques for solving recurrences are described with more detail in an old note I wrote a while ago (keeping the original tone and mistakes for authenticity):