 Parameterized complexity

Parameterized complexity studies an algorithm's resource use as a function of both the encoded input length $N$ and a distinguished nonnegative integer parameter $k$. A small solution size, a dimension or a structural property of a graph can serve as the parameter. Fixed-parameter tractability allows arbitrary computable dependence on $k$ while keeping the exponent of $N$ independent of $k$.