# Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries
## 3 Clustering in Stable Instances
### Phase 2 of Single-Linkage\(++\) (Removing the Edges)  
In this section, we focus on Phase 2 of the algorithm Single-Linkage\(++\), namely, computing the subset set \(K^{*}\) of \(k-1\) edges whose removal (from the tree \(T\) computed in Phase 1) yields the (unique) optimal clustering. This phase can also be seen as a matroid, though it is more complex than the one of the Single-Linkage (naive) algorithm because of these two issues:  
1. In order to evaluate the cost of a candidate solution (set \(K\) of edges to remove), we need to compute the centroids of each cluster;
2. The number of elements in the associated matroid is \(N=\binom{n-1}{k-1}\), though we are interested in extracting only one (the optimal \(K^{*}\)). Another caveat is that, since we shall try all \(N=\binom{n-1}{k-1}\) subsets, in order to ensure a correct answer with high probability, we need for the subroutine determining the \"correct\" centroids to succeed with sufficiently high probability. **Definition 4**. : _An \((\alpha,q)\)-centroids procedure is an algorithm, which, on inputting any optimal \(k\)-clustering \(C_{1},\ldots,C_{k}\), with probability at least \(1-q\) returns a tuple_  
\[(\tilde{c}_{1},\ldots,\tilde{c}_{k})=\mathsf{centroids}(C_{1},\ldots,C_{k})\]  
_of \(\alpha\)-approximate centroids,_  
\[Cost(C_{i},\tilde{c}_{i})\leq\alpha Cost(C_{i},c_{i})\]  
_where \(c_{i}=\operatorname*{arg\,min}_{x\in C_{i}}Cost(C_{i},x)\)._  
_For \(\alpha=1\), we have an exact centroid procedure that returns the optimal centroids \(c_{i}\) of each cluster \(C_{i}\)._  
**Definition 5**. : _Given a \(k\)-spanning tree \(T\), an \(\alpha\)-approximate removal is a subset of \(k-1\) edges such that the \(k\)-clustering obtained by removing these edges from \(T\) is \(\alpha\)-approximate._  
**Theorem 4**. : _Suppose there exists an \((\alpha,q)\)-centroids procedure \(\mathsf{centroids}\) using \(O\langle h_{CEN},l_{CEN}\rangle\) high-low operations. Then, there exists an algorithm, which, with probability at least \(1-q-\frac{1}{N}\), finds an \(\alpha\)-approximate removal using \(O\langle Nh_{CEN}+\log N,Nl_{CEN}+N\log N\rangle\) high-low operations in total._  
Proof. : Given any \(k\)-spanning tree \(T\), we simply try all possible candidate subsets \(K\) of \(k-1\) edges of \(T\), and find the one that corresponds to the optimum as follows. For each candidate subset \(K^{(a)}\), with \(a=1,\ldots,N\), we proceed as follows:  
1. Consider the corresponding clustering \(C_{1}^{(a)},\ldots,C_{k}^{(a)}\). This can be done by simply inspecting the nodes of each connected component when removing edges \(K^{(a)}\) from \(T\). 2. Run the procedure \(\mathsf{centroids}\) to compute (some) centroids for this candidate clustering, \((c_{1}^{(a)},\ldots,c_{k}^{(a)})=\mathsf{centroids}(C_{1}^{(a)},\ldots,C_{k} ^{(a)})\). This gives a set of edges from centroid \(c_{i}^{(a)}\) to the other elements of the cluster \(C_{i}^{(a)}\), for all clusters: \[E^{(a)}=\{(x,y)\in E\mid x\in C_{i}^{(a)}\text{ and }y=c_{i}^{(a)}\text{ for some }i\}\.\]  
We now observe two key properties of these (candidate) centroids. For each cluster \(  
and therefore  
\[d(E^{(opt)})\leq\alpha Cost(C^{(opt)})\.\]  
This implies that the candidate \(K^{(min)}=\arg\min_{K^{(a)}}d(E^{(a)})\) which minimizes \(d(E^{(a)})\) among the \(N\) candidates is indeed an \(\alpha\)-approximate removal:  
\[Cost(C^{(min)})\leq d(E^{(min)})\leq d(E^{(opt)})\leq\alpha Cost(C^{(opt)})\.\]  
The total high-low cost to create the list of all \(N\) elements is \(O\langle Nh_{CEN},Nl_{CEN}\rangle\). As observed above, with a probability of at least \(1-q\), the minimum in this list yields an \(\alpha\)-approximate removal. Each pairwise comparison between two elements, say \(d(E^{(a)})\) and \(d(E^{(b)})\), can be done with a _single_ call to our oracles, either \(O_{L}(E^{(a)},E^{(b)})\) or \(O_{H}(E^{(a)},E^{(b)})\). We can thus apply Lemma 4 and, with a probability of at least \(1-\frac{1}{N}\), find the minimum element using \(\langle\log N,N\log N\rangle\) high-low cost operations.