= Fixed-parameter tractability
{title2=$f(k)N^{O(1)}$}
= FPT
{c}
{synonym}
= Fixed-parameter tractable
{synonym}
= Fixed-parameter tractable problem
{synonym}
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^kN^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>.
Back to article page
