14
$\begingroup$

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?

$\endgroup$
21
$\begingroup$

A good place to start is "Parameterized Complexity Theory" by Jörg Flum and Martin Grohe, published by Springer.

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The scribe notes are not there anymore. Will you repost them? $\endgroup$ – Austin Buchanan Nov 28 '14 at 21:24
11
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Parameterized Algorithms by Cygan et. al. is a nice textbook.

https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf

$\endgroup$

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.