# Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries
## 3 Clustering in Stable Instances
### Phase 1: Compute a \"Good\" Spanning Tree  
In the previous section, we have assumed that we have given a MST \(T\). This task can be solved with the standard MST algorithm using \(O(n^{2})\) high-cost operations. A natural question is thus whether there is a strategy that uses less than \(o(n^{2})\) high-cost operations. This seems difficult if we insist on computing a MST, since any edge in the MST can potentially appear in every position of the sorted sequence of edges. A key observation is that we do not have to necessarily compute a MST, but we only need a spanning tree from which we can recover the optimal solution removing \(k-1\) edges. This is captured by the following definition. **Definition 3** (\(k\)-spanning tree). : _Let \((X,d)\) a metric space and let \(C^{*}_{1},\ldots,C^{*}_{k}\) be an optimal \(k\)-clustering. A tree \(T\) of this metric space is \(k\)-spanning if every subtree \(T[C^{*}_{i}]\) induced by \(C^{*}_{i}\) is connected._  
The definition essentially says that, by removing \(k-1\) edges from a \(k\)-spanning tree, we obtain a forest whose connected components correspond to the optimal solution. Implicit in the proof of [3] (see also [4]), in order to successfully compute the optimum, it suffices to have a \(k\)-spanning tree (and not necessarily a MST one). **Theorem 3** (due to [3]). : _The modification of Single-Linkage++ algorithm, where, in Phase 1, we compute a \(k\)-spanning tree, finds the unique optimal \(k\)-clustering in every \(\gamma\)-pertubation-stable instance, with \(\gamma\geq 2\)._  
We thus consider how to compute a \(k\)-spanning tree, instead of an exact MST. We first show the following key corollary of Lemma 1. **Corollary 1**. : _For any \(\gamma\)-perturbation-stable metric space \((X,d)\), with \(\gamma\geq 2\), and with optimal solution \(C_{1}^{*},\ldots,C_{k}^{*}\) the following holds. If \(x\in C_{i}^{*}\) and \(y\
otin C_{i}^{*}\), for some cluster \(C_{i}^{*}\), then it must hold that_  
\[d(x,y)>(\gamma-1)d(x,c_{i}^{*})\]  
_where \(c_{i}^{*}\) is the centroid of \(C_{i}^{*}\)._  
Proof. : Since \(y\in C_{j}^{*}\) for some \(j\) different from \(i\), we have  
\[d(x,y)\geq d(x,c_{j}^{*})-d(y,c_{j}^{*})>\gamma d(x,c_{i}^{*})-\frac{d(y,c_{i} ^{*})}{\gamma}\geq\gamma d(x,c_{i}^{*})-\frac{d(x,y)+d(x,c_{i}^{*})}{\gamma}\]  
where the first and last inequality are due to the triangle inequality, and the second inequality follows from Lemma 1. Then, by rearranging the terms, we obtain  
\[1+\frac{1}{\gamma}d(x,y)>(\gamma-\frac{1}{\gamma})d(x,c_{i}^{*})\]  
which implies the corollary after some simplification. Now, we are ready to prove a sufficient condition for a tree to be \(k\)-spanning, which we shall use below to derive an algorithm good performance guarantee. **Lemma 5** (sufficient condition for \(k\)-spanning tree). : _Consider a \(\gamma\)-perturbation-stable metric space (X,d), with \(\gamma>2\). Any \((1+\epsilon)\)-approximation \(\hat{T}\) of the MST \(T\), with \(\epsilon\leq\frac{(\gamma-2)}{n-1}w\) and \(w:=\frac{d_{\min}^{(X)}}{d_{\max}^{(X)}}\), is a \(k\)-spanning tree._  
Proof. : By contradiction, suppose \(\hat{T}\) is not a \(k\)-spanning tree. We show that it cannot be a \((1+\epsilon)\)-approximation of the MST \(T\). Since \(T\) is not \(k\)-spanning, there is an optimal cluster \(C\) such that \(\hat{T}[C]\) is not connected. Let \(C^{\prime}\) be a connected component of \(\hat{T}[C]\) that does not contain the centroid of \(C\). Let \(x\in C^{\prime}\) be a node that is connected with some other \(y\
otin C\). Consider the tree  
\[\hat{T}:=(\hat{T}\setminus\{(x,y)\})\cup\{(x,c)\}\]  
and observe that, for \(d:=d(x,c)\), we have  
\[d(\hat{T})= d(\hat{T})-d(x,y)+d(x,c)\] \[< d(\hat{T})-(\gamma-1)d(x,c)+d(x,c)=d(\hat{T})-(\gamma-2)d\]  
where the inequality is due to Corollary 1.