Question

I'm reading the paper MST Construction in O(log log n) Communication Rounds in a Clique and trying to understand the correctness analysis, in page 5.

It shows by induction on k (phase number), that the spanning tree, for every cluster F (from phase k), is indeed an MST fragment of that cluster of vertices.

The claim is of course trivial for the base case, as the clusters are singletons of vertices. To show the induction step, it suffices to show that each edge $e$ (where $X\left(e\right)=\left(F_{1},F_{2}\right),\ F_{1}\in\hat{F_{1}},\ F_{2}\in\hat{F_{2}}$, where $F_{1},F_{2}$ are the original clusters, that is, the connected components of the previous round, now contracted into one vertex, and $\hat{F_{1}},\hat{F_{2}}$ are their super clusters, that is, the connected components containing them, created as part of this procedure in phase $k$) chosen by the procedure Const_Frags is indeed a minimum weight outgoing edge (MWOE) of either $H_{1}=\underset{F\in\hat{F_{1}}}{\bigcup}F$ or $H_{2}=\underset{F\in\hat{F_{2}}}{\bigcup}F$. They assume wlog that $e$ was chosen as part of $F_1$'s $\mu$ lightest outgoing weight edges, and want to show that $e$ is indeed the MWOE of $H_1$. So they assume otherwise, that there exists $e'$ of lower weight than $e$ that is outgoing from $H_1$.

What I don't understand is, why do they assume that $e'$ is of cluster $F_1$ as well? The only thing we know about $e'$ is that it is outgoing from $H_1$. This means that it can be outgoing from another cluster- $F'\in\hat{F_{1}}\backslash\left\{ F_{1}\right\} $. I would appreciate any help! thanks!

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top