Parameterized complexity: Difference between revisions

Revision as of 19:42, 3 March 2005

Revision as of 19:51, 3 March 2005

Line 9:

:A parameterized problem <math>L</math> is ''fixed-parameter tractable'' if the question &ldquo;<math>(x, k) \in L</math>?&rdquo; can be decided in running time <math>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 [[Vertexthe vertex cover Cover]]problem in <math>O(kn + 1.29^k)</math> time, where <math>n</math> is the number of vertices and <math>k</math> the size of the vertex cover. This proves that Vertexvertex Covercover is fixed-parameter tractable with respect to this parameter.

[[Category:Computational complexity theory]]