4
$\begingroup$

Let $A$ an algorithm with polynomial time, which receives an graph $G$ and returns the stable set $S_A(G)$ of $G$ with the property:

$$ \alpha(G) - |S_A(G)| \le k, $$ for a constant $k\in N$

Prove that $A$ can be used for determining , in polynomial time, a stable set of maximum cardinal in a given graph.

I have tried by taking $T$ isomorphic copies of the graph and I have tried to extend the graph. But I get stuck at this point, can you give me some hints?

$\endgroup$
5
  • $\begingroup$ maybe k exists, but not any? $\endgroup$
    – kotomord
    Nov 7 '16 at 15:07
  • 1
    $\begingroup$ @kotomord Sorry, $k$ was actually a constant. I have fixed this mistake. $\endgroup$
    – cristid9
    Nov 7 '16 at 15:09
  • $\begingroup$ Using "|" where "\mid" should be used instead is a frequent error on this site, but this was the opposite mistake: "\mid" was used where "|" was appropriate. Notice how conspicuously different they look: $$ \alpha(G) - |S_A(G)| \le k, $$ $$ \alpha(G) - \mid S_A(G)\mid \le k, $$ Notice the lack of space to the left of the minus sign and to the left of the less-than-or-equal-to sign in the incorrect version. (And also the larger spaces surrounding $S_A(G)$.) There is a reason why it works that way, which should become clear if you think about it for a moment. $\qquad$ $\endgroup$
    – Michael Hardy
    Nov 7 '16 at 19:46
  • $\begingroup$ Is $k$ a fixed number or can we pick whatever $k$ we want? $\endgroup$
    – Aydin Gerek
    Nov 7 '16 at 20:50
  • $\begingroup$ @AydinGerek $k$ is said to be a constant. $\endgroup$
    – cristid9
    Nov 7 '16 at 20:55
3
+50
$\begingroup$

Create G1 as the k+1 copies of G.

$\endgroup$

Your Answer

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

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