2
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

I think I've found an answer, so will post here what I have. My proof seem to cover both scenarios I've mentioned. I still think their proof is incomplete. But in case I'm wrong, I would love to be corrected.

Similar to them assuming there is $e'$ outgoing from $F_1$, I assumed there was $e'$ outgoing from $F_3$ that is in $\hat{F_{1}}$, of lower weight than $e$.

If it was chosen, than it happened before choosing $e$, since its lighter. But then we get a contradiction to $e'$ being outgoing of $H_1$. So it wasn't chosen. If it wasn't chosen because it created a cycle, then it's yet again a contradiction to it being outgoing from $H_1$, since if it created a cycle, then $F_3, F_4$ were already merged by the time we reached $e'$, and therefore when we reached $e$ as well.

Therefore we're only left with the option that it was deemed "dangerous" (and therefore removed). Then either $e'\notin\mathcal{A}\left(F_{3}\right)$ or $\hat{F_{3}}$ was finished by the time we reached $e'$ .

If $\hat{F_{3}}$ was finished , then by the time we get to $e$ (which happens after $e'$, as $e'$ is lighter). But we assumed $F_3$ is part of $H_1$ by the time we reach $e$, therefore $\hat{F_{1}}$ is also finished, which is a contradiction to it being unfinished.

Then $e'\notin\mathcal{A}\left(F_{3}\right)$. This can happen for two reasons (as per their proof):

  • There exists a lighter (than $e'$) $e''$ in $\mathcal{A}\left(F_{3}\right)$ (such that $e''$ touches the same base fragments $e'$ touchs, which means its basically the same logical edge, just of lower weight). Therefore since $\hat{F_{3}}$ wasn't finished, and there were no cycles, $e''$ was added earlier than $e'$ and therefore than $e$. But then by the time we reach $e$, $e'$ is no longer outgoing from $H_1$. Contradiction yet again.

  • Then there exists $\mu$ lighter edges in $\mathcal{A}\left(F_{3}\right)$. Let $e''$ be the heaviest there (that is still lighter than $e'$ and therefore than $e$). Therefore after inspecting $e''$, $\hat{F_{3}}$ is deemed finished, which is yet again a contradiction.

$\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.