Parameterized complexity

Summary

Parameterized complexity measures the running time of an algorithm in terms of the input size and of a second number, the parameter. Its central class is FPT, the problems solvable in time $f(k) \cdot n^{c}$ with any function $f$ of the parameter $k$ and a constant $c$. It explains why some NP-hard problems are easy in practice when a parameter is small. The theory was developed by Downey and Fellows.