<p>Both the original <a href="http://rads.stackoverflow.com/amzn/click/038794883X" rel="noreferrer">parametrized complexity book by Downey and Fellows</a>, and the <a href="http://www2.informatik.hu-berlin.de/~grohe/pub/pkbuch.html" rel="noreferrer">newer book by Flum and Grohe</a>, are good references for reduction techniques. </p>

CC BY-SA 2.5
2011-02-13T08:17:47.577Z
Specifically, chapter 2 of the latter (titled: "Reductions and Parameterized Intractability") provides a good survey.
Sadeq Dousti
CC BY-SA 2.5
2011-02-13T11:19:20.320Z
I would also cite the book ["Invitation to Fixed-Parameter Algorithms"](http://theinf1.informatik.uni-jena.de/~niedermr/) by R. Niedermeier, in which the second part surveys several algorithmic methods.
Mathieu Chapelle
CC BY-SA 2.5
2011-02-13T20:20:20.613Z
See the FPT Wiki page for more resources http://fpt.wikidot.com/books-and-survey-articles
yzll
CC BY-SA 2.5
2011-02-13T07:58:52.897Z
2011-02-13T07:58:52.897Z
Suresh Venkat
<p>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 <a href="http://www-sop.inria.fr/mascotte/seminaires/AGAPE/notes" rel="nofollow">Spring School on Fixed Parameter and Exact Algorithms</a> (2009) may be a starting point. In particular, you may want to look at the following excellent overview talks:</p>

<ul>
<li>Dániel Marx on <em>FPT algorithmic techniques</em> (<a href="http://www-sop.inria.fr/mascotte/seminaires/AGAPE/lecture_notes/Agape%2009%20-%20Daniel%20Marx%20-%20FPT%20algorithmic%20techniques%20-%20Presentation.pdf" rel="nofollow">slides</a>).</li>
<li>Thore Husfeldt on <em>A Taxonomic Introduction to Exact Algorithms</em> (<a href="http://www-sop.inria.fr/mascotte/seminaires/AGAPE/lecture_notes/Agape%2009%20-%20Thore%20Husfeldt%20-%20A%20Taxonomic%20Introduction%20to%20Exact%20Algorithms%20-%20Slides.pdf" rel="nofollow">slides</a> | <a href="http://www-sop.inria.fr/mascotte/seminaires/AGAPE/lecture_notes/Agape%2009%20-%20Thore%20Husfeldt%20-%20A%20Taxonomic%20Introduction%20to%20Exact%20Algorithms.pdf" rel="nofollow">lecture notes</a>).</li>
</ul>

CC BY-SA 2.5
2011-02-13T15:52:36.087Z
2011-02-13T20:04:47.763Z
2011-02-13T20:04:47.763Z
Holger
<p>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)</p>

<p>Here it its table of contents :</p>

<p><a href="http://www.springerlink.com/content/978-3-642-16532-0#section=800200&amp;page=11&amp;locus=2" rel="nofollow">http://www.springerlink.com/content/978-3-642-16532-0#section=800200&amp;page=11&amp;locus=2</a></p>

<p>Nathann</p>

CC BY-SA 2.5
2011-02-14T21:07:07.797Z
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.
Mathieu Chapelle
CC BY-SA 2.5
2011-02-13T15:18:54.717Z
2011-02-13T15:18:54.717Z
Nathann Cohen
<p>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?</p>

CC BY-SA 2.5
2011-02-13T07:58:53.477Z
See [Wikipedia](http://en.wikipedia.org/wiki/Fixed-parameter_tractable#FPT) and the references thereof.
Sadeq Dousti
<cc.complexity-theory><reference-request><reductions><parameterized-complexity>
Any references for techniques in FPT reductions?
Regularity
# Any references for techniques in FPT reductions?

(Asked by: username_0 on 2011-02-13)

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?

**Tags:** cc.complexity-theory, reference-request, reductions, parameterized-complexity

> **Comments:**
> **username_1**: See [Wikipedia](http://en.wikipedia.org/wiki/Fixed-parameter_tractable#FPT) and the references thereof.  

---

## 3 answers

### Answer by username_2 on 2011-02-13. Score: 11

Both the original [parametrized complexity book by Downey and Fellows](http://rads.stackoverflow.com/amzn/click/038794883X), and the [newer book by Flum and Grohe](http://www2.informatik.hu-berlin.de/~grohe/pub/pkbuch.html), are good references for reduction techniques.

> **Comments:**
> **username_1**: Specifically, chapter 2 of the latter (titled: "Reductions and Parameterized Intractability") provides a good survey.  
> **username_3**: I would also cite the book ["Invitation to Fixed-Parameter Algorithms"](http://theinf1.informatik.uni-jena.de/~niedermr/) by R. Niedermeier, in which the second part surveys several algorithmic methods.  
> **username_4**: See the FPT Wiki page for more resources http://fpt.wikidot.com/books-and-survey-articles  

---

### Answer by username_5 on 2011-02-13. Score: 5

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](http://www-sop.inria.fr/mascotte/seminaires/AGAPE/notes) (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](http://www-sop.inria.fr/mascotte/seminaires/AGAPE/lecture_notes/Agape%2009%20-%20Daniel%20Marx%20-%20FPT%20algorithmic%20techniques%20-%20Presentation.pdf)).
* Thore Husfeldt on *A Taxonomic Introduction to Exact Algorithms* ([slides](http://www-sop.inria.fr/mascotte/seminaires/AGAPE/lecture_notes/Agape%2009%20-%20Thore%20Husfeldt%20-%20A%20Taxonomic%20Introduction%20to%20Exact%20Algorithms%20-%20Slides.pdf) | [lecture notes](http://www-sop.inria.fr/mascotte/seminaires/AGAPE/lecture_notes/Agape%2009%20-%20Thore%20Husfeldt%20-%20A%20Taxonomic%20Introduction%20to%20Exact%20Algorithms.pdf)).


---

### Answer by username_6 on 2011-02-13. Score: 3

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 :

<http://www.springerlink.com/content/978-3-642-16532-0#section=800200&page=11&locus=2>

Nathann

> **Comments:**
> **username_3**: 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.  

---

