# Reductions from non decision problems

I want to show a minimization problem $$Y$$ has no approximation factor of 1.36. To be more specific the problem $$Y$$ is the exemplar distance problem between two genomes. Could I reduce from the min vertex cover problem instead of the decision version of the vertex cover problem. The problem I am having with reducing from the decision version is that a vertex cover of size k maps to the $$Y$$ of size $$\leq ck$$, where $$c$$ is a constant. A decision version for problem $$Y$$ for me makes no sense, as there will always be a brekpoint distance between two genomes. I tried to research on the internet but I always only find reductions from decision problems. Could we reduce from non-decision problems.

Also when doing reductions from the vertex cover problem. I can't assume the given instance $$G,k$$ is such that k is the size of the optimal vertex cover right? $$k$$ is just any size of a Vertex cover.

• What you're talking about is hardness of approximation, it is big topic. So, start with approximation preserving reduction (there are many types of reductions) , then move to see complex technique that used PCP theorem. "see for example Vizirani's textbook and, Williamson and Shmoys's textbook to see examples". See the following lecture to see an overview of techniques in Inapproximabililty By Erik Demaine: youtube.com/watch?v=snugEmWtEm4 Nov 17 '19 at 12:52