Graph Theory - Max. Independent set algorithm

[oneamp]

Graph Theory -- Max. Independent set algorithm

Homework Statement

Design a polynomial time greedy algorithm to compute a maximum independent set for a graph. Explain the algorithm and compute T_w(n).

Homework Equations

The Attempt at a Solution

My terse and informal Internet research indicates that a maximum independent set cannot be calculated in polynomial time. For example:
http://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Finding_maximum_independent_sets

What could my teacher possibly want? Do I need to design an algorithm that nobody else to date has done? I guess not. I think I misunderstand the question. Can someone help me understand what he wants?

Thank you

 

[mfb]

Maybe "maximum independent set" is not meant in that way, and you are supposed to find an algorithm that finds an independent set where no other vertices can be added (should be easy in n^2). Just a guess, I don't know how the problem statement is meant.