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

CC BY-SA 3.0
2012-05-30T16:05:14.143Z
2012-05-30T16:05:14.143Z
David Harris
<p>I want to use multiple runs of maximal independent set (Luby's algorithm) to find a lower bound on the size of <strong>maximum</strong> independent set. </p>

<p>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 ?</p>

<p>The graphs don't possess any special properties.</p>

CC BY-SA 3.0
2012-05-30T14:04:24.153Z
What do you know about the question?  In other words, what have you tried to answer your own question?
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-30T14:16:18.200Z
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.
Graddy
CC BY-SA 3.0
2012-05-30T14:47:46.823Z
move to cs.stackexchange.com?
Sasho Nikolov
CC BY-SA 3.0
2012-05-30T14:56:32.770Z
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?
Sasho Nikolov
CC BY-SA 3.0
2012-05-30T17:27:15.063Z
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?
Jukka Suomela
CC BY-SA 3.0
2012-11-09T03:22:33.550Z
You need at least O(n^2) just to read the input.
Antimony
<ds.algorithms><reference-request><approximation-algorithms><randomized-algorithms>
Maximum Independent Set using Maximal MIS
Graddy
# Maximum Independent Set using Maximal MIS

(Asked by: username_0 on 2012-05-30)

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.

**Tags:** ds.algorithms, reference-request, approximation-algorithms, randomized-algorithms

> **Comments:**
> **username_1**: What do you know about the question?  In other words, what have you tried to answer your own question?  
> **username_0**: 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.  
> **username_2**: move to cs.stackexchange.com?  
> **username_2**: 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?  
> **username_3**: 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?  
> **username_4**: You need at least O(n^2) just to read the input.  

---

## 1 answers

### Answer by username_5 on 2012-05-30. Score: 2

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


---

