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.
- 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.
- 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.