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.


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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License