Parameterized complexity: Difference between revisions

Revision as of 15:20, 3 October 2019

Revision as of 22:37, 15 December 2019

Line 21:

=== 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>n^k</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 [[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 this problem is also in FPT.