Ken1 wrote: > I've been trying to do this for a while and now I give up, could > someone help me with this please. > > Given: undirected graph G and an integer k. > Does G contain an independent set of size of at least k? > > Basically, I need to prove that the k-independent-set problem is in NP. > I can easily prove it on paper but I can't figure out the algorithm for > this and it should be super simple. > > I need to prove that the correctness of a possible solution provided in > the form of a list of vertices can be verified in polynomial time. > > i found this: http://www.geocities.com/dharwadker/independent_set/ but > i cant seem to put it in a few lines of code > > i guess it should be something like 2 for loops... one inside the other > and then check that each neighbor of from the list is not connected to > the next in the solution... Grrr... =/ i dont see how to put it in > code. help please
--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
