Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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}$.
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.
