[Solved]: Why are all problems in FPTAS also in FPT?

There is actually a stronger result; A problem is in the class $mathrm{FPTAS}$ if it has an fptas1: an $varepsilon$-approximation running in time bounded by $(n+frac{1}{varepsilon})^{mathcal{O}(1)}$ (i.e. polynomial in both the size and the approximation factor). There’s a more general class $mathrm{EPTAS}$ which relaxes the time bound to $f(frac{1}{varepsilon})cdot n^{mathcal{O}(1)}$ – essentially an $mathrm{FPT}$-like running time with respect to the approximation factor. Clearly $mathrm{FPTAS}$ is a subset of $mathrm{EPTAS}$, and it turns out that $mathrm{EPTAS}$ is a subset of $mathrm{FPT}$ in the following sense:

Theorem If an NPO problem $Pi$ has an eptas, then $Pi$ parameterized by the cost of the solution is fixed-parameter tractable.

The theorem and proof is given in Flum & Grohe [1] as Theorem 1.32 (pp. 23-24), and they attribute it to Bazgan [2], which puts it two years before Cai & Chen’s weaker result (but in a French technical report). I’ll give a sketch of the proof, because I think it’s a nice proof of the theorem. For simplicity I’ll do the minimization version, just mentally do the appropriate inversions for maximization. Proof. Let $A$ be the eptas for $Pi$, then we can construct a parameterized algorithm $A’$ for $Pi$ parameterized by the solution cost $k$ as follows: given input $(x,k)$, we run $A$ on input $x$ where we set $varepsilon := frac{1}{k+1}$ (i.e. we choose the approximation ratio bound $1+frac{1}{k+1}$). Let $y$ be the solution, $text{cost}(x,y)$ be the cost of $y$ and $r(x,y)$ be the actual approximation ratio of $y$ to $text{opt}(x)$, i.e. $text{cost}(x,y) = r(x,y)cdot text{opt}(x)$. If $text{cost}(x,y) leq k$, then accept, as clearly $text{opt}(x) leq text{cost}(x,y) leq k$. If $text{cost}(x,y) > k$, reject as $r(x,y) leq 1+frac{1}{k+1}$ as $A$ is an eptas and $$ text{opt}(x) = frac{text{cost}(x,y)}{r(x,y)} geq frac{k+1}{1+frac{1}{k+1}} > k $$ Of course you get the running time bound for $A’$ simply from $A$ being an eptas. $Box$ Of course as Pål points out, parameterized hardness results imply the non-existence of any eptas unless there is some collapse, but there are problems in $mathrm{FPT}$ with no eptas (or even ptas), so $mathrm{EPTAS}$ is a strict subset of $mathrm{FPT}$ (in the sense of the theorem).

Footnotes:

1. An fptas (equivalently eptas or ptas) is an approximation scheme with the running time bounded as described above. The class $mathrm{FPTAS}$ (equiv. $mathrm{EPTAS}$, $mathrm{PTAS}$) is the set of problems in $mathrm{NPO}$ that have such a scheme.

[1]: J. Flum and M. Grohe, Parameterized Complexity Theory, Springer, 2006.
[2]: C. Bazgan. Schémas d’approximation et complexité paramétrée, Rapport de DEA, Université Paris Sud, 1995.