FIXED-PARAMETER ALGORITHMS AND PARAMETERIZED COMPLEXITY.

Parameterized complexity is a field of complexity theory pioineered in the 90's mainly by the works of Downey and Fellows and their coauthors.  In a nutshell, parameterized complexity challenges one of the main notions of traditional complexity theory, that a problem's complexity must be described as a function of the input size n, by introudicing a parameter, which is almost always denoted by k.  The role and meaning of the parameter vary wildly depending on the specific problem and application one might have in mind, but in general the parameter k is supposed to capture a property of the problem which helps us distinguish tractable from intractable instances.