Spanners and emulators with sublinear distance errors

Abstract

Let k ≥ 2 be an integer. We show that any undirected and unweighted graph G = (V, E) on n vertices has a subgraph G' = (V, E') with O(kn1+1/k) edges such that for any two vertices u, v ∈ V, if δG(u, v) = d, then δG'(u, v) = d+O(d1-1/k-1). Furthermore, we show that such subgraphs can be constructed in O(mn1/k) time, where m and n are the number of edges and vertices in the original graph. We also show that it is possible to construct a weighted graph G* = (V, E*) with O(kn1+1/(2k-1)) edges such that for every u, v ∈ V, if δG(u, v) = d, then δ ≤ δG*(u, v) = d + O(d1-1/k-1). These are the first such results with additive error terms of the form o(d), i.e., additive error terms that are sublinear in the distance being approximated.