For many fixed-parameter problems that are trivially soluable in polyn
omial time, such as (k-)DOMINATING SET, essentially no better algorith
m is presently known than the one which tries all possible solutions.
Other problems, such as (k-)FEEDBACK VERTEX SET, exhibit fixed-paramet
er tractability: for each fixed k the problem is soluable in time boun
ded by a polynomial of degree c, where c is a constant independent of
k. We establish the main results of a completeness program which addre
sses the apparent fixed-parameter intractability of many parameterized
problems. In particular, we define a hierarchy of classes of paramete
rized problems FPT subset of or equal to W[1] subset of or equal to W[
2] subset of or equal to ... subset of or equal to W[SAT] subset of or
equal to W[P] and identify natural complete problems for W[t] for t g
reater than or equal to 2. (In other papers we have shown many problem
s complete for W[1].) DOMINATING SET is shown to be complete for W[2],
and thus is not fixed-parameter tractable unless INDEPENDENT SET, CLI
QUE, IRREDUNDANT SET, and many other natural problems in W[2] are also
fixed-parameter tractable. We also give a compendium of currently kno
wn hardness results as an appendix.