-1
$\begingroup$

if by absurdly there is a 3/2-approximation algorithm for INDIPENDENT SET then does there exist a 3/2-approximation algorithm for VERTEX COVER? the implication should be true because independent is reduced to to VERTEX COVER, right?

$\endgroup$

1 Answer 1

2
$\begingroup$

Try to prove it. Don't just assume "it should be true"; write out the proof in detail. Specify the algorithm for finding a 3/2 approximation for Vertex Cover concretely. Provide a proof that its output is a 3/2 approximation.

If you try to do that, you should be able to answer your own question for yourself.

$\endgroup$
2
  • $\begingroup$ ok but what I ask is whether the implication is true or not in the absurd case that there is an approximation algorithm 3/2 for independent set? is approximability transitive? $\endgroup$ Commented Jul 5, 2023 at 10:26
  • $\begingroup$ @PatrickBateman, I suggest trying to prove or disprove it, following the approach that I outlined. If you spend some time on that and get stuck, you can edit the original question to clarify what you are asking and show what progress you've made. $\endgroup$
    – D.W.
    Commented Jul 5, 2023 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.