I would like to learn about Parametrized Complexity (both on the algorithmic side and on the hardness side). What books/lecture notes can I read on this subject?
$\begingroup$
$\endgroup$
Add a comment
|
7 Answers
$\begingroup$
$\endgroup$
A good place to start is "Parameterized Complexity Theory" by Jörg Flum and Martin Grohe, published by Springer.
$\begingroup$
$\endgroup$
1
Sorry for the self-advertisement, but this spring we have been developing a hybrid undergrad/grad course at Stanford on Parameterized Algorithms and Complexity. We've tried to "re-do" many of the proofs of the core theorems in the literature, in a way that's somewhat more accessible to undergraduates. The scribe notes are (mostly) online. However we have not carefully edited all of them, so I would not take the notes as gospel yet.
answered May 22, 2013 at 21:27
-
8$\begingroup$ The scribe notes are not there anymore. Will you repost them? $\endgroup$ Commented Nov 28, 2014 at 21:24
$\begingroup$
$\endgroup$
Daniel Marx has several interesting talks on FPT and related topics on his website. http://www.cs.bme.hu/~dmarx/
http://www.cs.bme.hu/~dmarx/talk.php
See also the recent collection of essays/book on the occasion of the 60th birthday of Mike Fellows. http://link.springer.com/book/10.1007/978-3-642-30891-8/page/1
Update (Nov 2014): Marek Cygan et al (long list of authors) have a book titled "Parameterized Algorithms" that should be coming out soon (to be published by Springer). I have seen drafts and it is quite nice. More algorithmic than the Flum-Grohe book and also covers several recent developments.
$\begingroup$
$\endgroup$
See http://fpt.wikidot.com/books-and-survey-articles. I also prefer Flum and Grohe, especially for the hardness part, whereas the book by Niedermeier is more focused on the algorithmic side. Note that there are some technical differences between the two, for instance the definition of a parameter as polynomial time computable function in the book of Flum and Grohe, which has to be altered if one likes to consider smaller parameterized space classes (see this article by Elberfeld, Stockhusen and Tantau).
$\begingroup$
$\endgroup$
1
What about the 1999 classical (first?) book on the topic by Rod Downey and Mike Fellows?
Two years ago, I heard that Rod and Mike were going to bring out a second edition of their book -- may be it is out now. Mike's website http://www.mrfellows.net should have more info. You can sign up for his mailing list (newsletter) which comes out every 2-3 months.
-
$\begingroup$ The 2nd edition is out (in 2015). The name of the book is Fundamentals of Parameterized Complexity . I feel that this book covers the basics in more detail than the famous book by Flum and Grohe. $\endgroup$ Commented Jul 27, 2019 at 14:49
$\begingroup$
$\endgroup$
A relatively new textbook is by Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh https://www.springer.com/in/book/9783319212746
$\begingroup$
$\endgroup$
2
Parameterized Algorithms by Cygan et. al. is a nice textbook.
https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf
-
$\begingroup$ this book is already included in kauray's answer: cstheory.stackexchange.com/a/42088/47855 $\endgroup$ Commented Jul 27, 2019 at 15:51
-
$\begingroup$ also given as update in Chandra Chekuri's answer: cstheory.stackexchange.com/a/17749/47855 $\endgroup$ Commented Jul 27, 2019 at 15:56