# On approximations and reductions

This may be a naive question but I am a bit clueless. I was under the opinion that given two NP complete problems, $P1$ and $P2$, if $P2 \in APX$ and $P1 \notin APX$, then we cannot have a direct reduction $P2\leq P1$ but we can have a reduction $P1\leq P2$.

In this paper on page 165 http://www.lancaster.ac.uk/staff/letchfoa/articles/cut-projection.pdf, there is a reduction $MAXCUT \leq STABLESET$. That is, given an instance of STABLESET, I can find an instance of MAXCUT. Why cant I use the approximate solution for MAXCUT to find an approximate solution to STABLESET?

## 1 Answer

In short, a reduction need not preserve approximations. For more details, see my answer on cstheory to a similar question.

• ah, i wanted to give the vertex-cover VS independent-set example, but Yuval is just too quick. Oct 2 '13 at 20:41