Slowest Link First

Eight datacenters, thirty candidate links, all latencies distinct. You must pick links so all eight are connected, and the only thing you are judged on is the slowest link in your chosen set. Total latency does not matter.

A teammate says the MST is the wrong tool because it minimises a sum, not a maximum, and proposes binary searching a latency threshold, keeping only links under it, and checking connectivity. Who is right?

Neither. Optimising over the largest edge calls for the maximum spanning tree.

The MST already solves it. Among all spanning trees, the MST also has the smallest possible largest edge, so the binary search lands on the same threshold and just does more work to get there.

The teammate is right. Minimising a sum and minimising a maximum are different objectives, so some other spanning tree can have a smaller largest edge than the MST does.

The MST works only because the latencies are distinct. With ties the MST is no longer unique and the bottleneck guarantee is lost, so the binary search is required.