1.  Luby Algorithm for Maximal Independent Set

1.1  definitions

1. G = (V,E) an undirected graph
2. I Í V is an independent set if no pairs of elements in I share an edge
3. I is a maximal independent set if "w Î V-I , {w}ÈI is not independent
4. I is a maximum independent set if "I¢, |I| ³ |I¢| . This problem is NP-hard or complete depending on how you phrase the problem.

1.2  algorithms

1.2.1 greedy lexicographic MIS

A maximal independent set algorithm is simple: grab the first vertex and run through the other vertices adding them to I if possible. This algorithm is O(m+n) .

This algorithm is P-complete, which means if this algorithm can be parallelized, every other parallel algorithm can be parallelized.

1.2.2 randomized parallel MIS

MIS(G)

1. Each vertex calculates it's own degree d(v) and tries to join S with probability [1/( 2d(v))]
2. if v,w Î S and share an edge, discard the one with a smaller degree. Break ties randomly, producing set I .
3. let V = V-I-N(I) where N(I) = the neighbor vertices in I and E = E minus all edges into I .
4. return IÈMIS(G)

1.2.3 Yet another MIS

MIS2(G)

1. Each vertex picks a random value, v Î [0,1]
2. v joins if it's value is less than the v¢s of it's neighbors, N(v)
3. let V = V-I-N(I) where N(I) = the neighbor vertices in I and E = E minus all edges into I .
4. return IÈMIS2(G)

The probability of joining is [1/( d+1)] which is a bit more aggresive than the previous algorithm.

1.2.4 Analysis

On a CRCW (concurrent read/concurrent write) architecture, steps 1 and 2 take constant time.

Unfortunately, it isn't true that a constant proportion of the vertices are lost each round. Instead, we can prove:

• v is 'good' if å_{u Î N(v)}[1/( 2d(u))] ³ ¹/₆

For the graph with n nodes completely connected to Ön nodes, K_n,Ön , each of the n nodes is 'bad' and the Ön nodes are 'good'.

• e = (v,w) is 'good' if v or w is 'good'.

• L(v) = {u Î N(v)|d(u) ³ d(v)}

The lemma follows pretty imediately.

In G direct all edges from low to high degree, then

proof by contradicition:

å_{u Î N(v)}[1/( 2d(u))] ³ å_{u Î In(v)}[1/( 2d(u))] ³ [(¹/₃d(v))/( 2d(v))] ³ ¹/₆

Now, we can construct a binomial tree in the graph where every leaf is 'good'. This implies the number of good edges satisfies: #bad+1 £ #good .