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

Problem Detail: 

According to the Wikipedia article on polynomial-time approximation schemes:

All problems in FPTAS are fixed-parameter tractable.

This result surprises me - these classes seem to be totally different from one another. FPTAS characterizes problems by how easy they are to approximate, while FPT characterizes problems by their difficulty relative to some parameter. Unfortunately, Wikipedia (as of the time I'm asking this question) doesn't provide a citation for this.

Is there a standard proof of this result? Or is there a source I could consult to learn more about this connection?

Asked By : templatetypedef

Answered By : Luke Mathieson

There is actually a stronger result; A problem is in the class $\mathrm{FPTAS}$ if it has an fptas¹: 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13679