• Overview
• Details
• Exercises

Fixed-parameter tractability studies algorithms whose running time is efficient for small parameter values, even if the problem is NP-hard in general. An FPT algorithm runs in time f(k) · n^O(1), where k is a parameter capturing structure (e.g., solution size, treewidth).

• Parameterized problems: instances (x, k); classifications FPT, XP; kernelization and problem kernels.
• Design techniques: bounded search trees, branching, iterative compression, color-coding, kernels via reduction rules.
• Examples: k-Vertex Cover in O(2^k n) and kernels of size O(k^2); k-Path via color-coding O*(2^k).
• Structural parameters: treewidth, vertex cover number; dynamic programming on tree decompositions.
• Hardness: W-hierarchy (W[1], W[2], ...); W[1]-hard problems (k-Clique); parameterized reductions.

1. Give a branching FPT algorithm for k-Vertex Cover and derive its recurrence and running time.
2. Design simple reduction rules yielding a polynomial kernel for Vertex Cover; prove correctness.
3. Implement color-coding to detect a simple path of length k in a graph and analyze expected runtime.