Editing Parameterized complexity (section)

=== FPT ===
FPT contains the ''fixed parameter tractable'' problems, which are those that can be solved in time <math>f(k) \cdot {|x|}^{O(1)}</math> for some computable function {{mvar|f}}. Typically, this function is thought of as single exponential, such as <math>2^{O(k)}</math>, but the definition admits functions that grow even faster. This is essential for a large part of the early history of this class. The crucial part of the definition is to exclude functions of the form <math>f(n,k)</math>, such as <math>k^n</math>.  

The class '''FPL''' (fixed parameter linear) is the class of problems solvable in time <math>f(k) \cdot |x|</math> for some computable function {{mvar|f}}.<ref>{{harvtxt|Grohe|1999}}</ref> FPL is thus a subclass of FPT. An example is the [[Boolean satisfiability]] problem, parameterised by the number of variables. A given formula of size {{mvar|m}} with {{mvar|k}} variables can be checked by brute force in time <math>O(2^km)</math>. A [[vertex cover]] of size {{mvar|k}} in a graph of order {{mvar|n}} can be found in time <math>O(2^kn)</math>, so the vertex cover problem is also in FPL.

An example of a problem that is thought not to be in FPT is [[graph coloring]] parameterised by the number of colors. It is known that 3-coloring is [[NP-hard]], and an algorithm for graph {{mvar|k}}-coloring in time <math>f(k)n^{O(1)}</math> for <math>k=3</math> would run in polynomial time in the size of the input. Thus, if graph coloring parameterised by the number of colors were in FPT, then [[P versus NP problem|P&nbsp;=&nbsp;NP]].

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)]].