Very sparse additive spanners and emulators

DOI10.1145/2688073.2688103MaRDI QIDQ2989053zbMATH OpenOpenAlexFDO

Authors Gregory Bodwin, Virginia Vassilevska Williams

Publication date 19 May 2017

Published in Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.05630

zbMATH Keywords

graph algorithmsgraph emulatorsgraph spanners

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers, which are sparse subgraphs that agree with the distances of the original graph on a given set of demand pairs. Prior work on distance preservers has exploited only a simple structural property of shortest paths, called consistency, stating that one can break shortest path ties such that no two paths intersect, split apart, and then intersect again later. We prove that consistency alone is not enough to understand distance preservers, by showing both a lower bound on the power of consistency and a new general upper bound that polynomially surpasses it. Specifically, our new upper bound is that any $p$ demand pairs in an $n$-node undirected unweighted graph have a distance preserver on $O(n^{2/3}{p}^{2/3}+n{p}^{1/3})$ edges. We leave a conjecture that the right bound is $O(n^{2/3}{p}^{2/3}+n)$ or better. The second part of this paper leverages these distance preservers in a new construction of additive spanners, which are subgraphs that preserve all pairwise distances up to an additive error function. We give improved error bounds for spanners with relatively few edges; for example, we prove that all graphs have spanners on $O(n)$ edges with $+O(n^{3/7+varepsilon})$ error. Our construction can be viewed as an extension of the popular path-buying framework to clusters of larger radii.

Recommendations

• A hierarchy of lower bounds for sublinear additive spanners
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• Efficient algorithms for constructing very sparse spanners and emulators
• The 4/3 additive spanner exponent is tight
• The 4/3 additive spanner exponent is tight

Cited in

(11)

• Thorup-Zwick emulators are universally optimal hopsets
• A hierarchy of lower bounds for sublinear additive spanners
• The 4/3 additive spanner exponent is tight
• scientific article; zbMATH DE number 7238981 (Why is no real title available?)
• Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
• New results on linear size distance preservers
• Approximate distance oracles with improved stretch for sparse graphs
• Improved weighted additive spanners
• Almost-optimal sublinear additive spanners
• Additive spanner lower bounds with optimal inner graph structure
• Lightweight near-additive spanners

This page was built for publication: Very sparse additive spanners and emulators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989053)