Techniques and Methodology

There are increasingly many powerful techniques for proving FPT or hardness results. Here are just a few pointers. Please help keep this updated.

Survey Papers

• Techniques for Practical Fixed-Parameter Algorithms. Falk Hüffner, Rolf Niedermeier, and Sebastian Wernicke. The Computer Journal 2008 51: 7-25; The Computer Journal.

• An Overview of Techniques for Designing Parameterized Algorithms. Christian Sloper and Jan Arne Telle. The Computer Journal 2008 51: 122-136. The Computer Journal.

Kernelization

• Slides of the talks given at the Third Workshop on Kernelization (WorKer 2011) in Vienna, Austria (click the link "Slides" after the talk title)
• Slides of Hans Bodlaender's tutorial on kernelization at IPEC 2011 in Saarbrucken, Germany
• Slides for Bart Jansen's talks (mostly kernelization-related)

Iterative Compression (A good project would be to find ways to use IC for maximization problems).

• Iterative Compression and Exact Algorithms. Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff and Saket Saurabh. Serge Gaspers'Website.

• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, Sebastian Wernicke. Journal of Computer and System Sciences, Volume 72 , Issue 8 (December 2006) Pages 1386-1396. portal.acm.

Crown Reductions

Multicolored Clique (W-Hardness)

Extremal Method and the Boundary Lemma (A good project would be to find ways to use this technique for minimization problems).