Maximal Steiner Trees in the Stochastic Mean-Field Model of Distance

Abstract

Consider the complete graph on $n$ vertices, with edge weights drawn independently from the exponential distribution with unit mean. Janson showed that the typical distance between two vertices scales as $\log n/n$, whereas the diameter (maximum distance between any two vertices) scales as $3\log n/n$. Bollobás et al. showed that, for any fixed k, the weight of the Steiner tree connecting $k$ typical vertices scales as $(k-1)\log n/n$, which recovers Janson's result for $k=2$. We extend this result to show that the worst case $k$-Steiner tree, over all choices of $k$ vertices, has weight scaling as $(2k-1)\log n/n$ and finally, we generalise this result to Steiner trees with a mixture of typical and worst case vertices.

16 pages