2
$\begingroup$

Given an optimization problem A which is NP-complete, and can be polynomially reduced to another optimization problem B which is also NP-complete. If we use an FPTAS to solve the reduced problem B' (A $\rightarrow$ B = B'), then under what rules can the solution obtained from solving with the FPTAS be directly associated with a solution to problem A?

For example, Problem A is shortest Path problem and Problem B is knapsack Problem.

$\endgroup$
3
  • $\begingroup$ You need the reduction to be approximation-preserving. $\endgroup$ Mar 24, 2016 at 18:12
  • $\begingroup$ @YuvalFilmus : Sorry for the trouble, but do you mind elaborating on it. If example is provided that will be quite helpful. But thanks for the note. $\endgroup$ Mar 24, 2016 at 19:10
  • $\begingroup$ Wikipedia has some information: en.wikipedia.org/wiki/Approximation-preserving_reduction. $\endgroup$ Mar 24, 2016 at 19:13

2 Answers 2

3
$\begingroup$

You need a stronger guarantee on the reduction, that it be approximation preserving. Not all reductions are approximation preserving. An extreme example is given by Min Vertex Cover and Max Independent Set. The complement of a vertex cover is an independent set, and so there are simple NP-hardness reductions between these problems. However, while Min Vertex Cover has a 2-approximation algorithm, Max Independent Set cannot be approximated to within $n^{1-\epsilon}$ for any $\epsilon > 0$ unless $\mathsf{P=NP}$.

$\endgroup$
3
$\begingroup$

You don't necessarily have to focus only on an FPTAS, and not even on positive results. The key idea is an approximation-preserving reduction: if you reduce problem A to problem B, then an $\alpha$-approximation algorithm for B implies a $f(\alpha)$-approximation for A, where $f$ is some function. Now observe both of the following are true: if A is hard to approximate, so is B. Also, if you can approximate B, you can also approximate A.

For example, consider an instance $(G,k)$ of chromatic number. Suppose there is a polynomial-time algorithm that, given $(G,k)$, constructs an instance $(G',k')$ of problem X. Moreover, suppose it holds that the size of $G'$ is linear in the size of $G$, $k' = k$, and $(G,k)$ is a YES-instance of chromatic number iff $(G',k')$ is a YES-instance of X. Now, any algorithm approximating problem X is also an approximation algorithm for chromatic number. But in fact, it is known chromatic number cannot be approximated within a factor of $n^{1-\varepsilon}$ for any $\varepsilon > 0$ (unless P = NP). Thus, the same is true for problem X.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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