# Distributed Graph Diameter Approximation
## 5 Implementation in the MapReduce Model
If \(G^{\prime}\) has a connected component of size \(k\) then it must have a tree of size \(k\). We prove the claim by showing that for \(c\geq 24d(d-1)\), the probability that a given vertex \(v\) is part of a tree of size \(k=c\log n\) is bounded by \(1/n^{2}\). For a fixed vertex \(v\in V\), let \(Y_{0}=\{v\}\) and let \(Y_{i}\) be the set of vertices in \(G^{\prime}\) connected to \(Y_{i-1}\) but not to \(Y_{j}\), \(j<i-1\), i.e.,  
\[Y_{i}=\{w\mid\exists(w,u)\in E^{\prime},\ w\
ot\in\cup_{i=0}^{i-1}Y_{i},\ u\in Y _{i-1}\},\]  
Consider a Galton-Watson branching process [32]\(\{Z_{i},\ i\geq 0\}\), with \(Z_{0}=1\), and \(Z_{i}=\sum_{j=1}^{Z_{i-1}}X_{j,i}\), where \(X_{j,i}\) are independent, identically distributed random variables with a Binomial distribution \(B(d-1,p)\). Clearly for any \(i\geq 0\), the distribution of \(Y_{i}\) is stochastically upper bounded by the distribution of \(Z_{i}\). For a branching process with i.i.d. offspring distributions as the one we are considering, the _total progeny_ can be bound as follows ([33], Theorem 3.13) [34]  
\[\Pr(\sum_{i\geq 0}Z_{i}\geq k)\leq\Pr(\sum_{i=1}^{k}X_{i}\leq k-1)\]  
where the \(X_{i}\) are independent random variables with the same distribution as the offspring distribution of the branching process, which in this case is a Binomial with parameters \((d-1)\) and \(p\). Now, we have \(E[\sum_{i=1}^{k}X_{i}]=k(d-1)p\), therefore, by applying a Chernoff bound, the probability that \(v\) is part of a tree of size \(\geq k\) is bounded by  
\[Pr(\sum_{i\geq 0}Y_{i}\geq k) \leq Pr(\sum_{i\geq 0}Z_{i}\geq k)\] \[\leq Pr(\sum_{i=1}^{k}X_{i}\geq k-1)\] \[\leq\exp\left(-\frac{k}{12d(d-1)}\right)\]  
If \(k=c\ln n\), with \(c\geq 24d(d-1)\), then we have  
\[Pr(\sum_{i\geq 0}Y_{i}\geq k)\leq\frac{1}{n^{2}}\]  
By union bound over the \(n\) nodes, the probability that the graph has a connected component of size greater than \(c\ln n\) is bounded by \(1/n\). On weighted graphs, the result of Lemma 2 immediately implies the following observation. **Observation 2**. : _Given a graph of maximum degree \(d\) with edge weights uniformly distributed in \([w_{\min},w_{max}]\), if we remove the edges whose weight is larger than or equal to \((w_{\min}+w_{max})/d\), then with high probability the graph becomes disconnected and the size of each connected component is \(O(\log n)\). That is, in any simple path the number of consecutive edges with weight less than \((w_{\min}+w_{max})/d\) is \(O(\log n)\), with high probability._  
Observation 2 allows us to derive the following corollary of Theorem 4. Recall that \(\Phi(G)\) denotes the weighted diameter of \(G\). With \(\Psi(G)\), instead, we denote its unweighted diameter. **Corollary 1**. : _Let \(G\) be a connected graph with \(n\) nodes, \(m\) edges, maximum degree \(d\in O(1)\), doubling dimension \(D\), and positive edge weights chosen uniformly at random from \([w_{\min},w_{max}]\), with \(w_{max}/w_{\min}=O(poly(n))\). Also, let \(\epsilon\in(0,1)\) be an arbitrarily fixed constant. With high probability, an estimate \(\Phi_{approx}(G)\) such that \(\Phi(G)\leq\Phi_{approx}(G)=O(\Phi(G)\log^{3}n)\), can be computed in_  
\[O\left(\left\lceil\frac{\Psi(G)}{n^{\epsilon/(2D)}}\right\rceil(\log n)^{3+2 /D}\right)\]  
_rounds on the \(MR(M_{L},M_{A})\) model with \(M_{L}=O(n^{\epsilon})\) and \(M_{A}=\Theta(m)\)._  
Proof. : Given the result of Theorem 4, in order to prove the corollary we only need to show the bound on the number of rounds. From the statement of Theorem 4, recall that, with high probability, the number of rounds is \(O(\ell_{4r_{c}^{2}}\log^{2}n)\), where \(r_{c}^{*}\) is the minimum radius of any clustering of \(G\) with at most \(n^{\epsilon/2}/\log^{2}n\) clusters. By iterating the definition of doubling dimension starting from a single ball of unweighted radius \(\Psi(G)\) containing the whole graph, we can decompose \(G\) into \(n^{\epsilon/2}/\log^{2}n\) disjoint clusters of unweighted radius \(\psi=O(\left\lceil\Psi(G)\log^{2}n/n^{\epsilon/2})^{1/D}\right\rceil)\).