As everyone knows, Garey and Johnson's famous book (and many others) provides an excellent reference for reduction technique in classical setting. Are there any surveys or books on the topic of reduction technique in parameterized algorithm, say the fpt reduction?

  • 1
    $\begingroup$ See Wikipedia and the references thereof. $\endgroup$ – M.S. Dousti Feb 13 '11 at 7:58

Both the original parametrized complexity book by Downey and Fellows, and the newer book by Flum and Grohe, are good references for reduction techniques.


Techniques for the design of algorithms often help in reductions as well. Therefore it may be good to learn about techniques used to design FPT algorithms, for which the notes of the Spring School on Fixed Parameter and Exact Algorithms (2009) may be a starting point. In particular, you may want to look at the following excellent overview talks:

  • Dániel Marx on FPT algorithmic techniques (slides).
  • Thore Husfeldt on A Taxonomic Introduction to Exact Algorithms (slides | lecture notes).

I haven't had the occasion to open it yet, but I guess you may be interested in "Exact exponential algorithms" by Fomin and Kratsch (from last year)

Here it its table of contents :



  • 2
    $\begingroup$ Notice that this book only surveys exact exponential algorithmic methods for solving and measuring the complexity of problems in the classical computational complexity point of view: dynamic programming, inclusion-exclusion, measure and conquer,... There is nothing in this book about any algorithmic reduction method, neither in classical computational complexity nor in parameterized complexity. $\endgroup$ – Mathieu Chapelle Feb 14 '11 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.