On fixed-parameter tractability and approximability of NP-hard optimization problems

Fixed-parameter tractability and approximability of NP-hard optimization problems are studied based on a model GC(s(n), Π_k^L). The main results are (1) a class of NP-hard optimization problems, including dominating-set and zero-one integer-programing, are fixed-parameter tractable if and only if GC(s(n ), Π₂^L)⊆P for some s(n)∈ ω(log n); (2) most approximable NP-hard optimization problems are fixed-parameter tractable. In particular, the class MAX NP is fixed-parameter tractable; (3) a class of optimization problems do not have fully polynomial time approximation scheme unless GC(s(n ),Π_k^L)⊆P for some s(n)∈ ω(log n) and for some k >l; and (4) every fixed-parameter tractable optimization problem can be approximated in polynomial time to a non-trivial ratio