your problem is a typical NPcomplete problem and no polynomial algorithm is possible. the link you provide just calculates maximal independent set, not maximum independent set. It turns out this two can be totally different.
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 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 -~----------~----~----~----~------~----~------~--~---
