A fixed-parameter-tractable algorithm, or FPT algorithm for short, gets an
instance (I, k) as its input and has to decide whether (I, k) is an element
of L for some parameterized problem L. Many parameterized algorithms work
in two stages: reduction to a problem kernel and bounded search tree. Their
time complexity is then of the form O(p(\I\) + q(k)xi(k)), where q(k) is t
he size of the problem kernel. We show how to modify these algorithms to ob
tain time complexity O(p(\I\) + xi k), if q(k) is polynomial. (C) 2000 Publ
ished by Elsevier Science B.V. All rights reserved.