FIXED-PARAMETER TRACTABILITY AND COMPLETENESS .2. ON COMPLETENESS FORW[1]

For many fixed-parameter problems that are trivially solvable in polyn omial-time, such as k-DOMINATING SET, essentially no better algorithm is presently known than the one which tries all possible solutions. Ot her problems, such as FEEDBACK VERTEX SET, exhibit fixed-parameter tra ctability: for each fixed k the problem is solvable in time bounded by a polynomial of degree c, where c is a constant independent of k. In a previous paper, the W Hierarchy of parameterized problems was define d, and complete problems were identified for the classes W[t] for t gr eater than or equal to 2. Our main result shows that INDEPENDENT SET i s complete for W[1].