Minimal Spanning Tree With Algorithms

Question

So I have a homework problem as above. The topic covered in class before this homework was Dynamic Programming. I have very little clue about what the question is actually asking: what is the MST actually for? What does it represent? How does it relate to CREW? How do I go about solving this question? Thanks for any help.

Answer 1

MST - as was said, by you is the minimum spanning tree of $G=(V, E)$, i.e. the spanning tree $T=(V,E')$, s.t. $E' \subseteq E$, $\lvert E' \rvert = n - 1$ and $T$ is connected, with the minimum weight.

The MST is useful in the context of minimizing costs for example. You are interested to cover some sites by some infrastructure (let say pipes), obviously you need each site to be connected by pipes, but as a business you want to minimize costs, i.e. to lay as little as absolutely necessary.

And you get the correctness for free from the correctness of Prim's algo.

Now, MST could be solved as offline problem by at least three well-known algorithms (Prim, Kruskal, Boruvka).

You have a different computation model, where $\lvert E \rvert$ processors got the input $e_i=(u,v)$ and $w(e_i)$ each, and by using some shared memory they try to produce MST.

I'll recall the Prim's algorithm for MST to get the idea of what the algorithm would be doing.

Basically, it grows the MST (T) one edge at a time. Initially, T contains an arbitrary vertex. In each step, T is augmented with a least-weight edge (x,y) such that x is in T and y is not yet in T.

It was called once a cut - the set of edges connecting vertices in already built $T$ to vertices not in $T$.

At each step we are interested to find the edge with the minimum weight in cut and add it to $T$ (in the end, after all vertices got added to $T$ we have an MST).

So if we able to pick this edge in $O(\log n)$ rounds, there are $n-1$ "pick-min" rounds to proceed until MST is "built".

The main building block: pick the minimum between $n$ numbers in $O(\log n)$ rounds.

• In zeroth round each processor $P_i$ writes its weight $w(e_i)$ in the memory cell $i$.
• In each further round $k$ the minimum weight holder between $2^k$ cells is elected. E.g. in round $1$ processors $P_0$ and $P_1$ are looking at memory cells $1$ and $0$ respectively, and each decides who's elected (in case of equal weights, the lower id is elected), and the min value is stored in the first cell of the block (i.e. in cell $0$). In round $2$ the winners of block $[0,1]$ and $[2,3]$ compare the values of cells at $0$ and $2$, etc.
• Since there are at most $n^2$ processors this stage takes at most $2 \log n + 1$ steps.
• We can dedicate some cell for overall winner of the stage to proclaim things (e.g. the id of added vertex or two).

To pick arbitrary the first vertex we can execute the above algorithm (since the lowest weight edge is always in MST). Not all the processors should participate in each stage. Only those that are in the current cut, so other processors should set their advertised weight to a $+\infty$ (i.e. value that is not participating, but if the pair is both not participating they still elect the winner with lower id)

We need $n-1$ such rounds, and the winner of each such round, should store the additional bit, that its edge is in MST (it's up to you how to read this information at algorithm's completion).

There is some hidden assumption that $w(e_i)$ fits in memory cell (i.e. takes $O(\log n)$ bits to be stored)