<p>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'$.</p>

<p>So, fixed-parameter tractability can be defined using either form equivalently.</p>

CC BY-SA 3.0
2015-08-13T11:57:54.017Z
Could you please provide a simple example?
Greg82
CC BY-SA 3.0
2015-08-11T05:43:30.280Z
2015-08-11T05:43:30.280Z
palindrome
<p>On <a href="http://fpt.wikidot.com/fpt" rel="nofollow">this page</a>, the definition of a Fixed-Parameter Tractable algorithm is given, followed by the very classical example, Vertex Cover.</p>

<p>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)})$ ?</p>

CC BY-SA 3.0
2015-08-08T15:02:44.390Z
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.
chazisop
CC BY-SA 3.0
2015-08-08T15:24:39.443Z
See https://en.wikipedia.org/wiki/Kernelization#Example:_vertex_cover , after this the size of the instance is upper bounded by $k^2$.
daniello
<cc.complexity-theory><parameterized-complexity><fixed-parameter-tractable>
FPT algorithm equivalent definitions
Greg82
# FPT algorithm equivalent definitions

(Asked by: username_0 on 2015-08-08)

On [this page](http://fpt.wikidot.com/fpt), 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)})$ ?

**Tags:** cc.complexity-theory, parameterized-complexity, fixed-parameter-tractable
> **Comments:**
> **username_1**: 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.  
> **username_2**: See https://en.wikipedia.org/wiki/Kernelization#Example:_vertex_cover , after this the size of the instance is upper bounded by $k^2$.  

---

## 1 answers

### Answer by username_3 on 2015-08-11. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: Could you please provide a simple example?  

---

