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-0 (2025-05-14):
Parameterized problems
- Video 4-1 (2025-05-14):
Fixed-parameter tractability
- Video 4-2 (2025-05-14):
Depth-bounded search I
- Video 4-3 (2025-05-14):
Problem kernels
- Video 4-4 (2025-05-20):
Problem kernels: p-MaxSAT
- Video 4-5 (2025-05-20):
Depth-bounded search for p-PlanarIndependentSet
- Video 4-6 (2025-05-20):
Depth-bounded search for p-ClosestString
- Video 4-7 (2025-05-21):
Depth-bounded search for p-ClosestString (part 2)
- Video 4-8 (2025-05-21):
Better FPT Vertex Cover & Linear recurrences
- Video 4-8 (2025-05-27):
Interleaving
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):