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.
If the graph is a clique (or a set of disconnected cliques), then Luby's algorithm succeeds on the first iteration.