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)

  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Apr 11 at 13:53
  • $\begingroup$ @YuvalFilmus they are exactly equal to each other: $f(U) = |S|$ if $S$ is the independent set $\endgroup$ – Beyond the Dark Apr 11 at 19:39
  • 1
    $\begingroup$ What is the number of vertices in the output of the reduction? $\endgroup$ – Yuval Filmus Apr 11 at 21:23
  • $\begingroup$ @YuvalFilmus From a graph $G$ with $|V|$ vertices I build a multigraph with $|V| + 2$ vertices $\endgroup$ – Beyond the Dark Apr 12 at 6:47
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 12 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.