A Hierarchy of Lower Bounds for Sublinear Additive Spanners
A Hierarchy of Lower Bounds for Sublinear Additive Spanners
Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say $\tilde{O}(n^{1+\delta})$ bits. There is an inherent tradeoff between the sparsity parameter $\delta$ and the stretch function $f$ of the compression scheme, but the qualitative nature of this …