Relation between fixed parameter and approximation algorithm

Question

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

Answer 1

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) 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), 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). See (Marx, The Computer Journal 2008) for a survey on FPT approximation.

Answer 2

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. J. Chen et al. / Discrete Applied Mathematics 155 (2007) 180 – 193.
2. Structure of Polynomial-Time Approximation. E. J. van Leeuwen et al. Technical Report UU-CS-2009-034, December 2009.