2016/05/03 by Bodwin, Greg
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1605.01106
Given p node pairs in an n-node graph, a distance preserver is a sparse subgraph that agrees with the original graph on all of the given pairwise distances. We prove the following bounds on the number of edges needed for a distance preserver: - Any p node pairs in a directed weighted graph have a distance preserver on O(n + n2/3 p) edges. - Any p = Ω((n2)/(rs(n))) node pairs in an undirected unweighted graph have a distance preserver on O(p) edges, where rs(n) is the Ruzsa-Szemerédi function from combinatorial graph theory. - As a lower bound, there are examples where one needs ω(σ2) edges to preserve all pairwise distances within a subset of σ= o(n2/3) nodes in an undirected weighted graph. If we additionally require that the graph is unweighted, then the range of this lower bound falls slightly to σ≤ n2/3 - o(1).