# Polynomial variable of inapproximability after reduction

I proved the inapproximability of a problem that, given a multigraph $$G = (V, E)$$ and a set of vertices $$U \subseteq V$$ tries to maximize a score $$f(U)$$ whose value depends on the edges of the graph, so it takes values in $$\{0, \dots, m\}$$, $$m$$ being the number of edges in the graph.

As the result was obtained by (exactly) reducing from the Maximum Independent Set which is known for being inapproximable within $$n^{1- \epsilon}$$, I am not sure how this is translated to my problem: Is it inapproximable within $$n^{1- \epsilon}$$ or within $$m^{1- \epsilon}$$ (as, in a certain sense, it counts the number of edges)?

(In the proof we build a multigraph in which each edge contributing to the score is associated with an independent vertex in the original graph and vice versa)

• The answer depends on your reduction. Can you spell out the properties satisfied by your reduction? That is, what is the relation between $\max f(U)$ and the size of the maximum independent set? – Yuval Filmus Apr 11 at 13:53
• @YuvalFilmus they are exactly equal to each other: $f(U) = |S|$ if $S$ is the independent set – Beyond the Dark Apr 11 at 19:39
• What is the number of vertices in the output of the reduction? – Yuval Filmus Apr 11 at 21:23
• @YuvalFilmus From a graph $G$ with $|V|$ vertices I build a multigraph with $|V| + 2$ vertices – Beyond the Dark Apr 12 at 6:47
• The $n$ in the inapproximability result for maximum independent set is the number of vertices. What I would suggest is writing out what it means for maximum independent set to be inapproximable within $n^{1-\epsilon}$, and then using your reduction to prove an inapproximability result for your problem. Instead of guessing what you get, prove it. – Yuval Filmus Apr 12 at 6:50