0
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ What do you know about the question? In other words, what have you tried to answer your own question? $\endgroup$ – Tsuyoshi Ito May 30 '12 at 14:04
  • $\begingroup$ 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. $\endgroup$ – Graddy May 30 '12 at 14:16
  • 2
    $\begingroup$ move to cs.stackexchange.com? $\endgroup$ – Sasho Nikolov May 30 '12 at 14:47
  • 2
    $\begingroup$ 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? $\endgroup$ – Sasho Nikolov May 30 '12 at 14:56
  • 2
    $\begingroup$ 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? $\endgroup$ – Jukka Suomela May 30 '12 at 17:27
2
$\begingroup$

If the graph is a clique (or a set of disconnected cliques), then Luby's algorithm succeeds on the first iteration.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.