# Graph Theory - Max. Independent set algorithm

1. Oct 24, 2013

### oneamp

Graph Theory -- Max. Independent set algorithm

1. The problem statement, all variables and given/known data

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

2. Relevant equations

3. 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

2. Oct 25, 2013

### Staff: Mentor

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.