Lesson 235
Parameterized Complexity & FPT
FPT · kernelization · W-hierarchy · treewidth
1:00How adding a second parameter k to complexity analysis can turn NP-hard problems into practical ones — and the theory behind fixed-parameter tractability, kernelization, and the W-hierarchy.
By the end, you can
- Explain what a parameter k is and why adding it to complexity analysis can make NP-hard problems tractable.
- State the FPT definition (f(k)·n^O(1)) and distinguish it from the XP form (n^O(k)).
- Compute 2^k·n and n^k for small values of k and n, and compare the magnitudes.
- Describe the bounded search tree algorithm for Vertex Cover and explain why it yields a 2^k·n bound.
- Apply the two kernelization reduction rules for Vertex Cover (delete isolated vertices; force high-degree vertices) and state the resulting 2k kernel bound.
- State the FPT-iff-kernel equivalence theorem.
- Place FPT, W[1], W[2], and XP in the correct nesting order and give a canonical complete problem for each non-FPT level.
- Explain what treewidth measures and state what Courcelle's theorem guarantees for bounded-treewidth graphs.
Up next in Theory of Computation & Compilers
