13
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Related, possibly duplicate ?: cstheory.stackexchange.com/questions/4906/… $\endgroup$ – Suresh Venkat Mar 20 '11 at 17:49
  • 1
    $\begingroup$ @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 $\endgroup$ – Prabu Mar 20 '11 at 17:59
  • $\begingroup$ but here i am looking for a relationship between approximation and fixed parameter. $\endgroup$ – Prabu Mar 20 '11 at 18:03
  • $\begingroup$ 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. $\endgroup$ – Saeed Mar 20 '11 at 19:08
16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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 $\endgroup$ – Prabu Mar 20 '11 at 14:57
  • $\begingroup$ 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? $\endgroup$ – XXYYXX Mar 20 '11 at 19:41
  • 1
    $\begingroup$ @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. $\endgroup$ – Yoshio Okamoto Mar 21 '11 at 6:22
  • $\begingroup$ @Prabu: I commented on your answer to the other question. @Yoshio: Thanks for answering @XXYYXX's question. $\endgroup$ – Serge Gaspers Mar 21 '11 at 13:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Falk Hüffner Mar 28 '11 at 10:36
7
$\begingroup$

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.
$\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.