Better distance preservers and additive spanners

DOI10.1137/1.9781611974331.CH61zbMATH Open1410.05034arXiv1505.05599OpenAlexW2953285790MaRDI QIDQ4575640FDOQ4575640

Authors: Greg Bodwin, Virginia Vassilevska Williams 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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.

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

Recommendations

• scientific article; zbMATH DE number 2079365
• Linear size distance preservers
• New results on linear size distance preservers
• Small stretch pairwise spanners and approximate \(D\)-preservers
• Sparse Distance Preservers and Additive Spanners

Mathematics Subject Classification ID

Distance in graphs (05C12)

Cited In (16)

• Graph spanners: a tutorial review
• Distance-Preserving Graph Contractions
• Distributed construction of purely additive spanners
• Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal
• New Results on Linear Size Distance Preservers
• Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts
• Approximate distance oracles with improved stretch for sparse graphs
• Title not available (Why is that?)
• Sparse Distance Preservers and Additive Spanners
• Improved weighted additive spanners
• Almost-optimal sublinear additive spanners
• Light Euclidean Spanners with Steiner Points
• New pairwise spanners
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Better distance preservers and additive spanners

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