Content deleted Content added
→W[P]: wikify |
Forgot an open parenthesis in the definition, and I guess an O |
||
Line 13:
:A ''parameterized problem'' is a language <math>L \subseteq \Sigma^* \times \N</math>, where <math>\Sigma</math> is a finite alphabet. The second component is called the ''parameter'' of the problem.
:A parameterized problem <math>L</math> is ''fixed-parameter tractable'' if the question “<math>(x, k) \in L</math>?” can be decided in running time <math>O(f(k) \cdot |x|^{O(1)})</math>, where <math>f</math> is an arbitrary function depending only on <math>k</math>. The corresponding complexity class is called '''FPT'''.
For example, there is an algorithm which solves the vertex cover problem in <math>O(kn + 1.274^k)</math> time, where <math>n</math> is the number of vertices and <math>k</math> is the size of the vertex cover. This proves that vertex cover is fixed-
| |||