Let A be a algorithm with polynomial time, which receives a graph G and returns the stable set SA(G) of G with the property:
\(\displaystyle alpha(G) - \mid SA(G) \mid <= 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 K+1 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 help?
\(\displaystyle alpha(G) - \mid SA(G) \mid <= 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 K+1 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 help?
