 Fixed-parameter tractability

A parameterized decision problem is fixed-parameter tractable if an algorithm decides every instance of encoded length $N$ and parameter $k$ in running time at most $f(k)N^c$, for a computable function $f$ and a constant $c$ independent of $k$. The distinction is in the exponent: $2^k{N}^3$ has this form, whereas an $N^k$ bound alone does not establish fixed-parameter tractability. Branching on an uncovered edge gives a fixed-parameter tractable vertex cover decision problem.