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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
