# 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