Compendium of Parameterized Problems

I'm currently maintaining a unofficial Compendium of Parameterized Problems.

This document includes a list of computational problems that have been studied within the framework of parameterized complexity. It is mainly based on the Compendium of Parameterized Complexity Results, version 2.0 (May 22, 1996), by Michael T. Hallett and H. Todd Wareham, and on Parameterized Complexity, R. G. Downey and M. R. Fellows, Springer-Verlag, 1999. This compendium includes, however, several new results that have been published in the last few years.

Every computational problem in this document has one or more parameterized versions. Currently there are 312 computational problems listed in alphabetical order. For each of them we report the known parameterized versions (for a grand-total of 376), the corresponding parameterized complexity results, and the references to the relevant articles in the bibliography.

This document does not pretend, of course, to be complete; for instance, it does not consider computational problems that are not decision problems.

Moreover, this document likely includes errors and omissions. If you have corrections, suggestions, new or missing results, please send them to compendium@bravo.ce.uniroma2.it.

Last update: September 15, 2006.

Available formats: