November 11th, 2016, 12:25 PM  #1 
Newbie Joined: Nov 2016 From: România Posts: 1 Thanks: 0  Graph Problem
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: 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? 

Tags 
graph, problem 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A graph problem in graph theory!  lubna_mira  Applied Math  0  January 12th, 2014 01:52 PM 
Graph problem.  FreaKariDunk  Calculus  5  May 31st, 2011 05:53 AM 
can you help me with a graph problem, please?  saihat  Applied Math  0  March 10th, 2009 05:06 PM 
Another Graph Problem  dajaka  Algebra  0  October 27th, 2008 09:12 AM 
Graph Problem  dajaka  Algebra  0  October 27th, 2008 09:10 AM 