Content deleted Content added
m →W[t]: fixed cs1 error |
→FPT: new parameter should be bounded in FPT reductions |
||
Line 29:
There are a number of alternative definitions of FPT. For example, the running time requirement can be replaced by <math>f(k) + |x|^{O(1)}</math>. Also, a parameterised problem is in FPT if it has a so-called kernel. [[Kernelization]] is a preprocessing technique that reduces the original instance to its "hard kernel", a possibly much smaller instance that is equivalent to the original instance but has a size that is bounded by a function in the parameter.
FPT is closed under a parameterised notion of [[Reduction (complexity)|reductions]] called '''''fpt-reductions'''''. Such reductions transform an instance <math>(x,k)</math> of some problem into an equivalent instance <math>(x',k')</math> of another problem (with <math>k' \leq g(k)</math>) and can be computed in time <math>f(k)\cdot p(|x|)</math> where <math>p</math> is a polynomial.
Obviously, FPT contains all polynomial-time computable problems. Moreover, it contains all optimisation problems in NP that allow an [[Efficient polynomial-time approximation scheme|efficient polynomial-time approximation scheme (EPTAS)]].
| |||