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.