# Maximum independent set given approximate oracle

Let $$A$$ be a polynomial time algorithm which receives a graph $$G$$ and returns a stable set $$SA(G)$$ of $$G$$ with the property: $$\alpha(G) - |SA(G)| \leq k$$, for some constant $$k$$.

Prove that $$A$$ could be used to determine, in polynomial time, a stable set of maximum cardinality in a certain given graph.

I have tried by taking a graph $$G_1$$ which is formed by disjoin union of $$k+1$$ copies of $$G$$. $$\alpha(G_1) = (K+1) \alpha(G)$$. I need to prove that $$|SA| = |SA(G_1)| / (k+1)$$ in order to complete the proof.

But I got stuck at this point. Any hints or help would be appreciated.

• – Yuval Filmus Nov 13 '16 at 7:48
• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Nov 13 '16 at 9:28
• @YuvalFilmus i saw that. But it doesn't help me out with this.. I tried as you said and i get stuck at that point.. How can i prove that |SA(G)| = |SA(G1)|/k+1 ? Is there another possibile way? – Boca Bogdan Nov 13 '16 at 12:01
• Unfortunately we can't just solve the exercise for you. I gave you a hint which should suffice. You need to work out the rest on your own. – Yuval Filmus Nov 13 '16 at 12:03
• I don't want full solution. I want to know if that is the right way to solve this. – Boca Bogdan Nov 13 '16 at 12:28