# Can we use reductions to design approximation algorithms for NP-hard problems?

Let us say that I have a problem $P(n)$ that I need to solve (where $n$ is the size of the input of problem $P$). I used a polynomial-time reduction from a known NP-hard problem $Q(m)$ (where $m$ is the size of the input of problem $Q$) to $P(n)$ and showed that $P(n)$ is NP-hard. The time complexity of the reduction is $O(n^k)$ for some fixed $k$.

Can I use a known approximation algorithm for problem $Q(m)$ that is $O(f(m))$-approximation for problem $Q(m)$ to design an approximation algorithm for problem $P(n)$ that is $O(g(n))$-approximation for problem $P(n)$?

• Yes, if your reduction is approximation-preserving. – Yuval Filmus Jan 26 '16 at 21:22
• What are your thoughts? Have you tried to prove that the answer is yes? If so, where did you get stuck? – D.W. Jan 26 '16 at 22:57
• Thank you for your thanks. For your information, comments are transitory and can be deleted at any time (e.g., when they've served their purpose, or if they are not aimed at improving the post or requesting clarification or providing additional information, roughly speaking). See cs.stackexchange.com/help/privileges/comment: "Comments are temporary "Post-It" notes" and see "When should I comment?". – D.W. Jan 27 '16 at 17:28