Spanners in randomly weighted graphs: independent edge lengths

Abstract

Given a connected graph $G=(V,E)$ and a length function $\ell :E\to \mathbb{R}$ we let $d_{v,w}$ denote the shortest distance between vertex $v$ and vertex $w$. A $t$-spanner is a subset $E^{\prime }\subseteq E$ such that if $d_{v,w}^{\prime }$ denotes shortest distances in the subgraph $G^{\prime }=(V,E^{\prime })$ then $d_{v,w}^{\prime }\le t{d}_{v,w}$ for all $v,w\in V$. We show that for a large class of graphs with suitable degree and expansion properties with independent exponential mean one edge lengths, there is w.h.p.~a 1-spanner that uses $\approx \frac{1}{2}n\log n$ edges and that this is best possible. In particular, our result applies to the random graphs $G_{n,p}$ for $np\gg \log n$.