# Distributed Graph Diameter Approximation
## 3 Clustering Algorithm
Let \(\gamma=4/\log e\) and define \(h\) as the smallest integer such that  
\[2^{h}\geq\gamma\cdot k^{*}\cdot\log n. \tag{1}\]  
Since \(k^{*}\leq n/\log^{2}n\), we can safely assume that \(1\leq h<\log n\) and define \(t=\log n-h\). For \(i\in[0,t)\), we define the event \(E_{i}=At\)_the end of iteration \(h+i\) of the for loop, at most \(n/2^{i}\) nodes are still uncovered._ We now prove that the event \(\cap_{i=0}^{t-1}E_{i}\) occurs with high probability. Observe that  
\[\Pr[\cap_{i=0}^{t-1}E_{i}]=\Pr[E_{0}]\cdot\prod_{t=1}^{t-1}\Pr[E_{i}|E_{0} \cap\cdots\cap E_{i-1}]=\prod_{t=1}^{t-1}\Pr[E_{i}|E_{0}\cap\cdots\cap E_{i-1}], \tag{2}\]  
where the first equality comes from the definition of conditional probability, and the second is due to the fact that \(\Pr[E_{0}]\) clearly holds with probability 1. Consider an arbitrary \(i\in[1,t)\), and assume that the event \(E_{0}\cap\cdots\cap E_{i-1}\) holds. We prove that, conditioned on this event, \(E_{i}\) holds with high probability. Let \(V_{i}\) be the set of nodes already covered at the beginning of iteration \(h+i\). By hypothesis, we have that \(|V\setminus V_{i}|\leq n/2^{i-1}\). We distinguish two cases. If \(|V\setminus V_{i}|\leq n/2^{i}\), then \(E_{i}\) clearly holds with probability 1. Otherwise, it must be  
\[\frac{n}{2^{i}}\leq|V\setminus V_{i}|\leq\frac{n}{2^{i-1}}. \tag{3}\]  
Let \(\mathcal{C}^{*}\) be a \(k^{*}\)-clustering of \(G\) with radius \(r\), whose existence is implied by the definition of \(k^{*}\), and divide its clusters into two groups: a cluster \(C\in\mathcal{C}^{*}\) is called _small_ if \(|C\cap(V\setminus V_{i})|<|V\setminus V_{i}|/(2k^{*})\), and _large_ otherwise. Let \(\mathcal{C}^{s}\) be the set of small clusters. We can bound the number of uncovered vertices contained in the small clusters as follows:  
\[\sum_{C\in\mathcal{C}^{s}}|C\cap(V\setminus V_{i})|\quad<\quad\sum_{C\in \mathcal{C}^{s}}\frac{|V\setminus V_{i}|}{2k^{*}}\quad\leq\quad\frac{|V \setminus V_{i}|}{2}\]  
It then follows that, overall, the _large clusters_ contain at least half of the nodes that the algorithm has yet to cover at the beginning of iteration \(h+i\). We now prove that, with high probability, at least one center will be selected in each large cluster. Consider an arbitrary large cluster \(C\). By Equations (1) and (3), we have that the number of uncovered nodes in \(C\) is at least  
\[\frac{|V\setminus V_{i}|}{2k^{*}}\geq\frac{n\cdot\gamma\cdot\log n}{2^{h+i+1}}.\]  
Since in iteration \(h+i\), an uncovered node becomes a center with probability \(2^{h+i}/n\), the probability that no center is selected from \(C\) is at most  
\[\left(1-\frac{2^{h+i}}{n}\right)^{|V\setminus V_{i}|/2k^{*}}\leq\left(1-\frac {2^{h+i}}{n}\right)^{\frac{\gamma\log n}{2^{h+i+1}}}\leq\exp\left(-\frac{ \gamma\log_{2}n}{2}\right)=\frac{1}{n^{2}}\]  
By applying the union bound over all large clusters and taking the complement of the probability, it immediately follows that the probability that each large cluster has at least one center being selected among its uncovered nodes is at least \(1-k^{*}/n^{2}\). Now, it is easy to see that in each iteration, in particular, in iteration \(h+i\), all nodes at distance at most \(2r\) from the newly selected centers will be covered by some cluster (either new or old). Consequently, since the radius of any cluster of \(\mathcal{C}\) is \(\leq r\), we have that with probability at least \(1-k^{*}/n^{2}\), at the end of iteration \(h+i\) all nodes in large clusters are covered. Thus, the nodes still uncovered at the of the iteration can belong only to small clusters in \(\mathcal{C}^{s}\), and, from what was observed before, there are at most \(|V\setminus V_{i}|/2\leq n/2^{i}\) of them. By multiplying the probabilities of the \(t<\log n\) conditional events \((E_{i}|E_{0}\cap\cdots\cap E_{i-1})\), we conclude that \(\cap_{i=1}^{t-1}E_{i}\) happens with probability at least \((1-k^{*}/n^{2})^{t}\geq 1-1/n\), where the last bound follows from [PERSON]'s inequality and the fact that \(k^{*}\leq n/\log^{2}n\).