# Maximum Independent Set using Maximal MIS

I want to use multiple runs of maximal independent set (Luby's algorithm) to find a lower bound on the size of maximum independent set.

Are there any bounds on the number of times the maximal algorithm has to be run to find the true maximum with a high probability ?

The graphs don't possess any special properties.

• What do you know about the question? In other words, what have you tried to answer your own question? May 30 '12 at 14:04
• My knowledge of approximation algorithms is minimal..the problem that I am working on was proven to be reducible to Maximum independent set but the graphs are so huge that even O(n^2) is practically impossible. The question was more of a reference request so that I can read up on the related material. May 30 '12 at 14:16
• move to cs.stackexchange.com? May 30 '12 at 14:47
• but in short maximum ind. set. is very very hard to approximate in general: not approximable within a factor of $n^{1-\epsilon}$ for any constant $\epsilon$. so look hard for special properties of your graph..bounded degree for example? May 30 '12 at 14:56
• Isn't it easy to show that you will need exponentially many iterations to find a maximum independent set, even if you study graphs of maximum degree 2? May 30 '12 at 17:27