11
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ This is a theorem of Cai and Chen (JCSS97), stating "if an NP optimization problem has a fully polynomial-time approximation scheme, then it is fixed-parameter tractable." See the paper On Fixed-Parameter Tractability and Approximability of NP Optimization Problems. $\endgroup$ – Pål GD Aug 8 '13 at 22:10
  • $\begingroup$ And, of course, as a corollary you get "The NP optimization problems that are $W[1]$-hard under the uniform reduction have no fully polynomial-time approximation scheme unless $W[1] = FPT$." $\endgroup$ – Pål GD Aug 8 '13 at 22:15
  • $\begingroup$ @PålGD- Though it does seem that the choice of parameterization is somewhat arbitrary; they choose the parameter to be value of the optimal solution for the problem input. I suppose that technically works, though it's intellectually not very fulfilling. $\endgroup$ – templatetypedef Aug 8 '13 at 23:44
  • $\begingroup$ Luke Mathieson gave a very nice answer below, and I think that suffices to answer your question. $\endgroup$ – Pål GD Aug 9 '13 at 11:06
14
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.