0
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Asked before: cs.stackexchange.com/questions/65685/stable-set-algorithm. $\endgroup$
    – Yuval Filmus
    Nov 13 '16 at 7:48
  • $\begingroup$ 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! $\endgroup$
    – Raphael ♦
    Nov 13 '16 at 9:28
  • $\begingroup$ @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? $\endgroup$
    – Boca Bogdan
    Nov 13 '16 at 12:01
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Nov 13 '16 at 12:03
  • $\begingroup$ I don't want full solution. I want to know if that is the right way to solve this. $\endgroup$
    – Boca Bogdan
    Nov 13 '16 at 12:28

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.