Randomized Algorithm Probability Maximization

I'm a computer science undergrad and I'm just studying for finals. I came across a problem that was kind of out of place with the various dynamic programming type problems. I'll summarize it like this:

I'm given an efficient randomized algorithm, A, that returns an independent set. This algorithm returns the maximum independent set with probability at least 1/(n^3) where n is th开发者_高级运维e number of vertices in the graph. Suggest another algorithm, using A, that returns the maximum set with probability at least 1/2.

I've studied randomized algorithms, but this just seems like a simple case of implementation. If I was to run A n^3 times, the probability that the maximum independent set is close to 1. Could I then say that running it n^3/2 times would give the desired effect? Am I just trying to make this harder? Any help is appreciated.

Close but not accurate, the probability for one of the runs to return the correct answer is at least 1/n^3. That means that the probability of getting the wrong answer in one run is (1-1/n^3), which means the probability of getting the right answer after M runs is 1-(1-1/n^3)^M.

Now recall the formula for e (Wikipedia link), if you run n^3 times, the probability is 1-1/e which is more than 1/2 (although not very close to 1), it is also trivial to get the exact number of runs to get to exactly 1/2 - (n^3)*ln(2).

I haven't study the maximum independent set so I cannot give you too much help. However, you should first write out the algorithm first before claiming the number of running time.

If you run the algorithm A for n^3, you get n^3 maximum independent set. However, you need to return only ONE maximum set. How do you figure out the correct one within those n^3? Here you may want a verification algorithm that is missing in your question.

Depending on the problem itself (maximum independent set), it is possible for you to have enough information to find the correct maximum independent set that requires number of running much less than O(n^3).