main page — CS 627 Advanced Algorithms
Unit 4: Fixed-Parameter Algorithms
This is an archived version of this module from Summer 2025.
Click here for the current iteration.
This unit covers
- Fixed-parameter tractability
- Depth-bounded search trees
- Kernelization
- Linear recurrences
Material
- slides
- Video 4-0 (2025-05-14, 14:46):
Parameterized problems
- Video 4-1 (2025-05-14, 33:25):
Fixed-parameter tractability
- Video 4-2 (2025-05-14, 11:11):
Depth-bounded search I
- Video 4-3 (2025-05-14, 24:28):
Problem kernels
- Video 4-4 (2025-05-20, 21:50):
Problem kernels: p-MaxSAT
- Video 4-5 (2025-05-20, 43:13):
Depth-bounded search for p-PlanarIndependentSet
- Video 4-6 (2025-05-20, 11:22):
Depth-bounded search for p-ClosestString
- Video 4-7 (2025-05-21, 15:53):
Depth-bounded search for p-ClosestString (part 2)
- Video 4-8 (2025-05-21, 1:04:49):
Better FPT Vertex Cover & Linear recurrences
- Video 4-8 (2025-05-27, 42:13):
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):