I don't understand the exact relation between between FPT and FPTAS. Specifically, given an optimization problem P with fptas A does that imply that for any parameter (a computable map from the input to the integers) there is an FPT algorithm? It's standard that given an FPTAS, there is an FPT algorithm parameterized by the solution cost. (see: Why are all problems in FPTAS also in FPT?).

Does the existence of an FPTAS have any bearing on the FPT status of a problem with given (i.e. not necessarily solution cost) parameter k? Thanks.

  • $\begingroup$ Why do you expect there to be such a connection? The acronyms might look similar but they stand for two very different concepts. $\endgroup$ Sep 3, 2017 at 10:56
  • $\begingroup$ I don't in general. I'm trying to show the hardness of a problem in XP for which an FPTAS is known and I'm worried I'm on a fool's errand. Namely I couldn't find (for example) a problem in scheduling on m machines with a fptas for constant m, but also W hard in the number of machines. $\endgroup$
    – sosu
    Sep 3, 2017 at 16:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.