Parameterized complexity: Difference between revisions

Revision as of 10:05, 20 January 2010

Revision as of 10:11, 20 January 2010

Line 26:

===FPT===

FPT contains the ''fixed parameter tractable'' problems, which are those that can be solved in time <math>O(f(k)|x|^{O(1)})</math> for some computable function ''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>n^k</math>.

An example is the [[satisfiability]] problem, parameterised by the number of variables. A given formula of size ''m'' with ''k'' variables can be checked by brute force in time <math>O(2^km)</math>. A [[vertex cover]] of size ''k'' in a graph of size ''m'' can be found in time <math>O(2^km)</math>, so this problem is also in FPT.

An example of a problem that is not supposed 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 ''k''-colouring in time <math>O(f(k)n^{O(1)})</math> for ''k''=3 would run in polynomial time in the size of the input. Thus, if graph colouring were in FPT, then P=NP.

There are a number of alternative definitions of FPT. In particular, the running time requirement can be replaced by <math>O(f(k) + |x|^{O(1)})</math>. Also, a parameterised problem is in FPT if it has a so-called kernel. Kernelisation is a precomputation technique reducing the original instance to its “hard kernel”, a much smaller instance that is in some sense computationally equivalent to the original instance but of size polynomial in the parameter.

Obviously, FPT contains all polynomial-time computable problems. Moreover, it contains all optimisation problems in NP that allow a [[Fully polynomial-time approximation scheme]].

===W[1]===