# Distributed Graph Diameter Approximation
## 4 Diameter Approximation Strategy  
We are now ready to describe our clustering-based strategy to approximate the diameter of a graph \(G\). For any fixed value \(r>0\), we run RandCluster\((G,r)\) to obtain a clustering \(\mathcal{C}\). By Theorem 2, we know that, with high probability, \(\mathcal{C}\) has radius \(r_{\mathcal{C}}\leq 2r\log n\) and consists of \(O(k^{*}\log^{2}n)\) clusters, where \(k^{*}\) is the minimum number of clusters among all the clusterings of \(G\) with radius \(r\). Also, we recall that \(\mathcal{C}\) is represented by the tuples \((u,c_{u},d_{u})\), for every \(u\in V\), where \(c_{u}\) is the center of the cluster of \(u\), and \(d_{u}\leq r_{\mathcal{C}}\) is an upper bound to \(d(u,c_{u})\). As in [16], we define a weighted auxiliary graph \(G_{\mathcal{C}}\) associated with \(\mathcal{C}\) where the nodes correspond to the cluster centers and, for each edge \((u,v)\) of \(G\) with \(c_{u}\
eq c_{v}\), there is an edge \((c_{u},c_{v})\) in \(G_{\mathcal{C}}\) of weight \(w(u,v)+d_{u}+d_{v}\). In case of multiple edges between clusters, we retain only the one yielding the minimum weight. (See Figure 3 for the auxiliary graph associated to the clustering described in Figure 2). Figure 2: A specific execution of RandCluster on the weighted graph depicted in (**a**), with \(r=2\). In Iteration \(i=1\) of the **for** loop, only node \(A\) is (randomly) selected, and the two growing steps (**b**), (**c**) are performed. The resulting partial cluster centered at \(A\) is highlighted in red. In Iteration 2, two further centers, \(M\) and \(R\), are selected, and only one growing step (**d**) is executed. The resulting final clusters are highlighted in red, green, and brown. Let \(\Phi(G)\) (resp., \(\Phi(G_{\mathcal{C}})\)) be the diameter of \(G\) (resp., \(G_{\mathcal{C}}\)). We approximate \(\Phi(G)\) with  
\[\Phi_{\mathrm{approx}}(G)=\Phi(G_{\mathcal{C}})+2\cdot r_{\mathcal{C}} \tag{4}\]  
It is easy to see that \(\Phi_{\mathrm{approx}}(G)\geq\Phi(G)\). The following theorem provides an upper bound to \(\Phi_{\mathrm{approx}}(G)\). **Theorem 3**. : _If \(r=O(\Phi(G))\), then_  
\[\Phi_{approx}(G)=O\left(\Phi(G)\log^{3}n\right),\]  
_with high probability._  
Proof. : Since \(r_{\mathcal{C}}\leq 2r\log n\), and, by hypothesis, \(r=O(\Phi(G))\), it is sufficient to show that \(\Phi(G_{\mathcal{C}})=O(\Phi(G)\log^{3}n)\). To this purpose, let us fix an arbitrary pair of distinct clusters \(C_{1},C_{2}\) and a shortest path \(\pi\) in \(G\) between their centers of (minimum) weight \(w_{\pi}\). Let \(\pi_{C}\) be the (not necessarily simple) path of clusters in \(G_{\mathcal{C}}\) traversed by \(\pi\), and observe that, by shortcutting all cycles in \(\pi_{C}\), we have that the distance between the nodes associated to the centers of \(C_{1}\) and \(C_{2}\) in \(G_{\mathcal{C}}\) is upper bounded by \(w_{\pi}\) plus twice the sum of the radii of the distinct clusters encountered by \(\pi_{C}\). We now show that, with probability at least \(1-1/n^{3}\), this latter sum is \(O(\Phi(G)\log^{3}n)\). Then the theorem will immediately follow by applying the union bound over all pairs of distinct clusters. We distinguish the following two cases. **Case 1. ** Suppose that \(2r>\Phi(G)\) (hence, \(r=\Theta(\Phi(G))\), since we assumed \(r=O(\Phi(G))\)) and let \(i\geq 1\) be the index of the first iteration where some centers are selected. By applying a standard Chernoff bound ([31], Corollary 4.6) we can easily show that \(O(\log n)\) centers are selected in Iteration \(i\), with probability at least \(1-1/n^{3}\). Moreover, since all nodes in \(G\) are at light distance at most \(\Phi(G)\) from the selected centers, we have that, by virtue of Observation 1, all nodes will be covered by the end of Iteration \(i\). Therefore, with probability at least \(1-1/n^{3}\), \(\pi_{C}\) contains \(O(\log n)\) clusters and it easily follows that its weight is \(O(w_{\pi}+r\log n)=O(w_{\pi}+\Phi(G)\log n)=O(\Phi(G)\log^{3}n)\). **Case 2. ** Suppose now that \(2r\leq\Phi(G)\).