On this page, the definition of a Fixed-Parameter Tractable algorithm is given, followed by the very classical example, Vertex Cover.

But how the complexity given for Vertex Cover, $O(kn+1.274^k)$ (which is on the form $O(f(k) + |x|^{O(1)})$) is related to the definition, that gives a complexity of the form $O(f(k)⋅|x|^{O(1)})$ ?

  • 3
    $\begingroup$ Well, one could simply add an extra $n$ and set $f(k) = 1 + 1.274^{k}$. Even the wikipedia page says that the addition form is acceptable too, what we wanted to avoid is "inter-dependence" of the form $n^k$ or similar. $\endgroup$
    – chazisop
    Aug 8 '15 at 15:02
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/Kernelization#Example:_vertex_cover , after this the size of the instance is upper bounded by $k^2$. $\endgroup$
    – daniello
    Aug 8 '15 at 15:24

It's not hard to show that a function $g(n,k)$ is $O(f(k)\cdot n^c)$ for some computable function $f$ and constant $c$ if and only if $g(n,k)$ is $O(f'(k) + n^{c'})$ for some computable function $f'$ and constant $c'$.

So, fixed-parameter tractability can be defined using either form equivalently.

  • $\begingroup$ Could you please provide a simple example? $\endgroup$
    – Greg82
    Aug 13 '15 at 11:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.