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$
  • $\begingroup$ You need the reduction to be approximation-preserving. $\endgroup$ – Yuval Filmus Mar 24 '16 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$ – letsBeePolite Mar 24 '16 at 19:10
  • $\begingroup$ Wikipedia has some information: en.wikipedia.org/wiki/Approximation-preserving_reduction. $\endgroup$ – Yuval Filmus Mar 24 '16 at 19:13
2
$\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}$.

| cite | improve this answer | |
$\endgroup$
2
$\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.

| cite | improve this answer | |
$\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.