<p>There is known theorem [1,Theorem 3.1], characterizing approximation class <span class="math-container">$FPTAS$</span> through parameterized class <span class="math-container">$PFPT$</span>:</p>
<blockquote>
<p>Let <span class="math-container">$Q=(I_Q, S_Q, f_Q, opt_Q)$</span> be a scalable <span class="math-container">$NP$</span> optimization problem. Then <span class="math-container">$Q$</span> has an <span class="math-container">$FPTAS$</span> if and only if <span class="math-container">$Q$</span> is in <span class="math-container">$PFPT$</span>.</p>
</blockquote>
<p>In turn, <span class="math-container">$PFPT$</span> is defined as:</p>
<blockquote>
<p>An <span class="math-container">$NP$</span> optimization problem <span class="math-container">$Q$</span> is polynomial fixed-parameter tractable (<span class="math-container">$PFPT$</span>) if its parameterized version is solvable in time <span class="math-container">$O(|x|^{O(1)}k^{O(1)})$</span>, where <span class="math-container">$|x|$</span> - the size of the input instance <span class="math-container">$x$</span>.</p>
</blockquote>
<p>Another characterizations for two approximation classes are proposed in [2,Theorem 6.5].</p>
<blockquote>
<p>A problem is</p>
<ul>
<li><p>in <span class="math-container">$PTAS$</span> if and only if it has a <span class="math-container">$ptas^{\infty}$</span> and its standard parameterization is in <span class="math-container">$XP^w$</span>.</p>
</li>
<li><p>in <span class="math-container">$FPTAS$</span> if and only if it has an <span class="math-container">$fptas^{\infty}$</span> with a polynomially-bounded threshold function and its standard parameterization is in <span class="math-container">$PFPT^w$</span>.</p>
</li>
</ul>
</blockquote>
<p>Here <span class="math-container">$(f)ptas^{\infty}$</span> means asymptotic (fully) polynomial approximation scheme, standard parametrization - decision version of an optimization problem, <span class="math-container">$(XP)PFPT^w$</span> - corresponding classes of decision problems for which an algorithm which decides them returns a witness if the answer is Yes, threshold function - function depending on error <span class="math-container">$\frac{1}{\epsilon}$</span> and bounding from below an optimum value.</p>
<ol>
<li><a href="http://books.google.com/books?hl=en&amp;lr=&amp;id=zw_phoON4EkC&amp;oi=fnd&amp;pg=PA500#v=onepage&amp;q&amp;f=false" rel="noreferrer">Polynomial time approximation schemes and parameterized complexity</a>. J. Chen et al. / Discrete Applied Mathematics 155 (2007) 180 – 193.</li>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.159.2135&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Structure of Polynomial-Time Approximation</a>. E. J. van Leeuwen et al. Technical Report UU-CS-2009-034, December 2009.</li>
</ol>

CC BY-SA 2.5
2011-03-21T15:49:06.947Z
2011-03-21T16:52:58.007Z
2020-06-17T09:38:08.363Z
Oleksandr Bondarenko
<p>There are several connections between parameterized complexity and approximation algorithms.</p>

<p>First, consider the so-called standard parameterization of a problem. Here, the parameter is what you would optimize in the optimization version of the problem (the size of the vertex cover for the Vertex Cover problem, the width of the tree decomposition for the Treewidth problem, etc.). Let us concretely look at Vertex Cover. Any kernel with a linear number of vertices for Vertex Cover implies a constant factor polynomial-time approximation algorithm: into the approximate solution, put all the vertices that have been forced into the solution by the kernelization algorithm, and all the vertices of the kernelized instance. On the other hand, lower bounds on the approximation factor imply lower bounds on the size of a kernel. For example, under the Unique Games Conjecture, <a href="http://dx.doi.org/10.1016/j.jcss.2007.06.019" rel="nofollow">Khot and Regev (JCSS 2008)</a> rule out approximation algorithms for Vertex Cover with a ratio of any $c&lt;2$, which rules out a kernel for Vertex Cover with at most $ck$ vertices, $c&lt;2$, as well.</p>

<p>EDIT: The argumentation for the kernel lower bound in the previous paragraph is very informal, and to the best of my knowledge it is open whether such lower bounds on the kernel size can be proven, even for Vertex Cover. As @Falk points out in the comments, the argument holds for most (all?) known kernels. However, I don't see how one could exclude the existence of kernelization algorithms where a feasible solution of the kernelized instance has a different approximation ratio than the corresponding solution in the initial instance.</p>

<p>Then, there is the issue of PTAS versus FPTAS. If we want to find a solution within $(1+\epsilon)$ from optimal, we can parameterize by $1/\epsilon$. Then, a PTAS corresponds to an XP-algorithm in the parameterized setting, whereas an FPTAS corresponds to an FPT-algorithm. For an approximation lower bound, we may not expect an EPTAS for any problem whose standard parameterization is W[1]-hard: running the EPTAS with $\epsilon=1/(k+1)$ would solve the problem exactly in FPT time.</p>

<p>Finally, an FPT approximation algorithm is an algorithm with FPT running time and an approximation ratio which may depend on the parameter. For example, the standard parameterization of the Cliquewidth problem has an FPT approximation algorithm with approximation ratio $(2^{3k+2}-1)/k$ <a href="http://dx.doi.org/10.1007/11604686_5" rel="nofollow">(Oum, WG 2005)</a>, whereas the standard parameterization of Independent Dominating Set has no FPT approximation algorithm with performance ratio $g(k)$ for any computable function $g$, unless FPT=W[2] <a href="http://dx.doi.org/10.1007/11847250_11" rel="nofollow">(Downey et al., IWPEC 2006)</a>. See <a href="http://dx.doi.org/10.1093/comjnl/bxm048" rel="nofollow">(Marx, The Computer Journal 2008)</a> for a survey on FPT approximation.</p>

CC BY-SA 2.5
2011-03-20T14:57:14.593Z
@Gasper Can you please see the question "Finding a maximum acyclic sub-tournament given two acyclic sub-tournaments" . I still have doubt with my answer. As you have worked with related problem, you can help me out
Prabu 
CC BY-SA 2.5
2011-03-20T19:41:34.750Z
IS the first paragraph of Serge's answer correct? Does the lower bound on approximability yield lower bound on the size of the kernel? The similar statement is in Niedermeier's book but is this statement correct?
XXYYXX
CC BY-SA 2.5
2011-03-21T06:22:05.817Z
@XXYYXX: In Serge's answer, he wrote "Any kernel with a linear number of vertices for Vertex Cover implies a constant factor polynomial-time approximation algorithm" with a short proof. More precisely, his argument shows if there exists a kernel with ck vertices for some constant c, then there exists a factor-c approximation algorithm. The contrapositive is: if no factor-c approximation algorithm exists, then no kernel with ck vertices exists.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-21T13:35:41.873Z
@Prabu: I commented on your answer to the other question.
@Yoshio: Thanks for answering @XXYYXX's question.
Serge Gaspers
CC BY-SA 2.5
2011-03-24T13:48:56.627Z
I still don't understand why a kernel would imply an approximation. The graph produced by a kernelization does not need to have anything to do with the original graph; in particular, it does not have to be a subgraph. So I don't see how "vertices that have been forced into the solution" and "vertices of the kernelized instance" are well-defined.
Falk Hüffner
CC BY-SA 2.5
2011-03-25T12:58:48.140Z
@Falk (and @XXYYXX): I agree that my argument is not very formal (Section 14.1 in Niedermeier's book does not contain more details either). The kernelized instance $(G',k')$ must however be somehow related to the original instance $(G,k)$, as $(G',k')$ is a yes-instance iff $(G,k)$ is a yes-instance. I had a situation in mind where one vertex of $G'$ corresponds to exactly one vertex in $G$. Is it reasonable to assume otherwise, given that if $k'<k$, I would run the kernelization algorithm again?
Serge Gaspers
CC BY-SA 2.5
2011-03-28T10:36:54.740Z
In fact for probably all known kernelizations, the argument holds. However, I see no reason why there shouldn't be one that e.g. first reduces to another problem, kernelizes there, and then reduces back to Vertex Cover, so that the resulting instance has no vertex correspondence with the initial one. So it seems to me that the only thing we can really show is that kernels that are subgraphs will probably not be smaller than 2k.
Falk Hüffner
CC BY-SA 3.0
2011-03-20T14:11:55.707Z
2011-05-25T18:09:37.330Z
2011-05-25T18:09:37.330Z
Serge Gaspers
<p>Fixed parameter and approximation are totally different approaches to solve hard problems. They have different motivation. Approximation looks for faster result with approximate solution. Fixed parameter looks for exact solution with time complexity in terms of the exponential or some function of k and polynomial function of n where n is the input size and k is parameter. Example $2^kn^3$.</p>

<p>Now my question, is there any upper or lower bound result based on the relationship between fixed parameter and approximation approaches or they totally do not have any relationship.For example for a problem $P$ is said to be $W[i]$ hard for some $i&gt;0$ is nothing to do with having c-approximation algorithm or PTAS. please provide some references</p>

CC BY-SA 2.5
2011-03-20T17:49:37.050Z
Related, possibly duplicate ?: http://cstheory.stackexchange.com/questions/4906/hardness-of-fpt-problems
Suresh Venkat
CC BY-SA 2.5
2011-03-20T17:59:51.283Z
@suresh venkat That question is about difference in understand NP-complete and fixed parameter. when we talk in terms of NP-hardness only, then independent set and vertex cover are literally same, but when we talk in terms of fixed parameter they have huge difference. vertex cover has good fpt whereas independent set is W[1] hard
Prabu 
CC BY-SA 2.5
2011-03-20T18:03:04.917Z
but here i am looking for a relationship between approximation and fixed parameter.
Prabu 
CC BY-SA 2.5
2011-03-20T19:08:58.727Z
I think there is no real relation between them, but by using fixed parameter we may have a good approximation, for example in bin packing (makespan scheduling) you can see this relation, or for example in bounded Treewidth graphs we have approximations on some problems.
Saeed
<cc.complexity-theory><reference-request><approximation-algorithms><fixed-parameter-tractable>
Relation between fixed parameter and approximation algorithm
Prabu 
# Relation between fixed parameter and approximation algorithm

(Asked by: username_0 on 2011-03-20)

Fixed parameter and approximation are totally different approaches to solve hard problems. They have different motivation. Approximation looks for faster result with approximate solution. Fixed parameter looks for exact solution with time complexity in terms of the exponential or some function of k and polynomial function of n where n is the input size and k is parameter. Example $2^kn^3$.

Now my question, is there any upper or lower bound result based on the relationship between fixed parameter and approximation approaches or they totally do not have any relationship.For example for a problem $P$ is said to be $W[i]$ hard for some $i>0$ is nothing to do with having c-approximation algorithm or PTAS. please provide some references

**Tags:** cc.complexity-theory, reference-request, approximation-algorithms, fixed-parameter-tractable
> **Comments:**
> **username_1**: Related, possibly duplicate ?: http://cstheory.stackexchange.com/questions/4906/hardness-of-fpt-problems  
> **username_0**: @suresh venkat That question is about difference in understand NP-complete and fixed parameter. when we talk in terms of NP-hardness only, then independent set and vertex cover are literally same, but when we talk in terms of fixed parameter they have huge difference. vertex cover has good fpt whereas independent set is W[1] hard  
> **username_0**: but here i am looking for a relationship between approximation and fixed parameter.  
> **username_2**: I think there is no real relation between them, but by using fixed parameter we may have a good approximation, for example in bin packing (makespan scheduling) you can see this relation, or for example in bounded Treewidth graphs we have approximations on some problems.  

---

## 2 answers

### Answer by username_4 on 2011-03-20. Score: 16 | Accepted answer

There are several connections between parameterized complexity and approximation algorithms.

First, consider the so-called standard parameterization of a problem. Here, the parameter is what you would optimize in the optimization version of the problem (the size of the vertex cover for the Vertex Cover problem, the width of the tree decomposition for the Treewidth problem, etc.). Let us concretely look at Vertex Cover. Any kernel with a linear number of vertices for Vertex Cover implies a constant factor polynomial-time approximation algorithm: into the approximate solution, put all the vertices that have been forced into the solution by the kernelization algorithm, and all the vertices of the kernelized instance. On the other hand, lower bounds on the approximation factor imply lower bounds on the size of a kernel. For example, under the Unique Games Conjecture, [Khot and Regev (JCSS 2008)](http://dx.doi.org/10.1016/j.jcss.2007.06.019) rule out approximation algorithms for Vertex Cover with a ratio of any $c<2$, which rules out a kernel for Vertex Cover with at most $ck$ vertices, $c<2$, as well.

EDIT: The argumentation for the kernel lower bound in the previous paragraph is very informal, and to the best of my knowledge it is open whether such lower bounds on the kernel size can be proven, even for Vertex Cover. As @Falk points out in the comments, the argument holds for most (all?) known kernels. However, I don't see how one could exclude the existence of kernelization algorithms where a feasible solution of the kernelized instance has a different approximation ratio than the corresponding solution in the initial instance.

Then, there is the issue of PTAS versus FPTAS. If we want to find a solution within $(1+\epsilon)$ from optimal, we can parameterize by $1/\epsilon$. Then, a PTAS corresponds to an XP-algorithm in the parameterized setting, whereas an FPTAS corresponds to an FPT-algorithm. For an approximation lower bound, we may not expect an EPTAS for any problem whose standard parameterization is W[1]-hard: running the EPTAS with $\epsilon=1/(k+1)$ would solve the problem exactly in FPT time.

Finally, an FPT approximation algorithm is an algorithm with FPT running time and an approximation ratio which may depend on the parameter. For example, the standard parameterization of the Cliquewidth problem has an FPT approximation algorithm with approximation ratio $(2^{3k+2}-1)/k$ [(Oum, WG 2005)](http://dx.doi.org/10.1007/11604686_5), whereas the standard parameterization of Independent Dominating Set has no FPT approximation algorithm with performance ratio $g(k)$ for any computable function $g$, unless FPT=W[2] [(Downey et al., IWPEC 2006)](http://dx.doi.org/10.1007/11847250_11). See [(Marx, The Computer Journal 2008)](http://dx.doi.org/10.1093/comjnl/bxm048) for a survey on FPT approximation.

> **Comments:**
> **username_0**: @Gasper Can you please see the question "Finding a maximum acyclic sub-tournament given two acyclic sub-tournaments" . I still have doubt with my answer. As you have worked with related problem, you can help me out  
> **username_5**: IS the first paragraph of Serge's answer correct? Does the lower bound on approximability yield lower bound on the size of the kernel? The similar statement is in Niedermeier's book but is this statement correct?  
> **username_6**: @XXYYXX: In Serge's answer, he wrote "Any kernel with a linear number of vertices for Vertex Cover implies a constant factor polynomial-time approximation algorithm" with a short proof. More precisely, his argument shows if there exists a kernel with ck vertices for some constant c, then there exists a factor-c approximation algorithm. The contrapositive is: if no factor-c approximation algorithm exists, then no kernel with ck vertices exists.  
> **username_4**: @Prabu: I commented on your answer to the other question. @Yoshio: Thanks for answering @XXYYXX's question.  
> **username_7**: I still don't understand why a kernel would imply an approximation. The graph produced by a kernelization does not need to have anything to do with the original graph; in particular, it does not have to be a subgraph. So I don't see how "vertices that have been forced into the solution" and "vertices of the kernelized instance" are well-defined.  
> **username_4**: @Falk (and @XXYYXX): I agree that my argument is not very formal (Section 14.1 in Niedermeier's book does not contain more details either). The kernelized instance $(G',k')$ must however be somehow related to the original instance $(G,k)$, as $(G',k')$ is a yes-instance iff $(G,k)$ is a yes-instance. I had a situation in mind where one vertex of $G'$ corresponds to exactly one vertex in $G$. Is it reasonable to assume otherwise, given that if $k'<k$, I would run the kernelization algorithm again?  
> **username_7**: In fact for probably all known kernelizations, the argument holds. However, I see no reason why there shouldn't be one that e.g. first reduces to another problem, kernelizes there, and then reduces back to Vertex Cover, so that the resulting instance has no vertex correspondence with the initial one. So it seems to me that the only thing we can really show is that kernels that are subgraphs will probably not be smaller than 2k.  

---

### Answer by username_3 on 2011-03-21. Score: 7

There is known theorem [1,Theorem 3.1], characterizing approximation class $FPTAS$ through parameterized class $PFPT$:

> Let $Q=(I\_Q, S\_Q, f\_Q, opt\_Q)$ be a scalable $NP$ optimization problem. Then $Q$ has an $FPTAS$ if and only if $Q$ is in $PFPT$.

In turn, $PFPT$ is defined as:

> An $NP$ optimization problem $Q$ is polynomial fixed-parameter tractable ($PFPT$) if its parameterized version is solvable in time $O(|x|^{O(1)}k^{O(1)})$, where $|x|$ - the size of the input instance $x$.

Another characterizations for two approximation classes are proposed in [2,Theorem 6.5].

> A problem is
>
> * in $PTAS$ if and only if it has a $ptas^{\infty}$ and its standard parameterization is in $XP^w$.
> * in $FPTAS$ if and only if it has an $fptas^{\infty}$ with a polynomially-bounded threshold function and its standard parameterization is in $PFPT^w$.

Here $(f)ptas^{\infty}$ means asymptotic (fully) polynomial approximation scheme, standard parametrization - decision version of an optimization problem, $(XP)PFPT^w$ - corresponding classes of decision problems for which an algorithm which decides them returns a witness if the answer is Yes, threshold function - function depending on error $\frac{1}{\epsilon}$ and bounding from below an optimum value.

1. [Polynomial time approximation schemes and parameterized complexity](http://books.google.com/books?hl=en&lr=&id=zw_phoON4EkC&oi=fnd&pg=PA500#v=onepage&q&f=false). J. Chen et al. / Discrete Applied Mathematics 155 (2007) 180 – 193.
2. [Structure of Polynomial-Time Approximation](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.159.2135&rep=rep1&type=pdf). E. J. van Leeuwen et al. Technical Report UU-CS-2009-034, December 2009.


---

