# Distributed Graph Diameter Approximation
## 4 Diameter Approximation Strategy
We show that, with high probability, at most \(O(\lceil w_{\pi}/r\rceil\log^{2}n)\) clusters intersect \(\pi\) (i.e., contain nodes of \(\pi\)). Observe that \(\pi\) can be divided into \(O(\lceil w_{\pi}/r\rceil)\) subpaths, where each subpath is either an edge of weight \(>r\) or a segment of weight \(\leq r\). We next show that the nodes of each of the latter segments belong to \(O(\log^{2}n)\) clusters, with high probability. Consider one such segment \(S\). Clearly, all clusters containing nodes of \(S\) must have their centers at light distance at most \(2r\log n\) from \(S\) (i.e., light distance at most \(2r\log n\) from the closest node of \(S\)). For \(1\leq j\leq 2\log n+1\), let \(C(S,j)\) be the set of nodes whose light distance from \(S\) is between \((j-1)r\) and \(j\cdot r-1\), and observe that any cluster intersecting \(S\) must be centered at a node belonging to one of the \(C(S,j)\)'s. We claim that, with high probability, for any \(j\), there are \(O(\log n)\) clusters centered at nodes of \(C(S,j)\) which may intersect \(S\). Fix an index \(j\), with \(1\leq j\leq 2\log n+1\), and let  
Figure 3: Auxiliary graph \(G_{\mathcal{C}}\) associated to the clustering \(C\) of radius \(r_{C}=5\) described in Figure 2. Observe that the diameter \(\Phi(G)\) of the original graph \(G\) (Figure 2a) is realized by the path \(\langle L,A,E,I,M,P,Q,R,S\rangle\) of weight \(16\), while the algorithm returns the value \(\Phi_{\mathrm{approx}}(G)=\Phi(G_{\mathcal{C}})+2\cdot r_{\mathcal{C}}=12+2 \times 5=22\). be the first iteration of the for loop of RandCluster in which some center is selected from \(C(S,j)\). By Observation 1, \(\lceil((j+1)r-1)/(2r)\rceil\) iterations are sufficient for any of these centers to cover the entire segment. On the other hand, any center from \(C(S,j)\) needs at least \(\lceil(j-1)r/(2r)\rceil\) iterations to touch the segment. Hence, we have that no center selected from \(C(S,j)\) at Iteration \(i_{j}+2\) or higher can cover a node of \(S\), since by the time it reaches \(S\), the nodes of the segment are already covered and stable. We now show that the number of centers being selected from \(C(S,j)\) in Iterations \(i_{j}\) and \(i_{j}+1\) is \(O(\log n)\). For a suitable constant \(c\), we distinguish two cases. 1. \(|C(S,j)|\leq c\log n\). Then the bound trivially holds. 2. \(|C(S,j)|>c\log n\). Let \(h\) be an index such that in Iteration \(h\) the center selection probability \(p_{h}=2^{h}/n\) is such that \(p_{h}\cdot|C(S,j)|=c\log n\). Therefore, in Iteration \(h+1\) the expected number of centers selected from \(C(S,j)\) is \(2c\log n\). By applying the Chernoff bound, we can prove that, with high probability, the number of centers selected from \(C(S,j)\) in Iteration \(h+1\) is \(\Theta(\log n)\) and that the number of centers selected in any iteration \(\leq h+1\) is \(O(\log n)\). Furthermore, observe that, with high probability, \(i_{j}\leq h\): indeed, if no center is selected in iterations up to the \(h-1\), with high probability at least one is chosen at iteration \(h\), since we just proved that \(\Theta(\log n)\) are selected in iteration \(h\). Therefore, we have that the total number of centers selected from \(C(S,j)\) in Iterations \(i_{j}\) and \(i_{j}+1\) (and thus the only centers from \(C(S,j)\) which may cover nodes of \(S\)) is \(O(\log n)\). Overall, considering all \(C(S,j)\)'s, the nodes of segment \(S\) will belong to \(O(\log^{2}n)\) clusters, with high probability. By applying the union bound over all segments of \(\pi\), we have that \(O(\lceil w_{\pi}/r\rceil\log^{2}n)\) clusters intersect \(\pi\), with high probability. It is easy to see that by suitably selecting the constants in all of the applications of the Chernoff bound, the high probability can be made at least \(1-1/n^{3}\).