We make improvements to the upper bounds on several popular types of distance preserving graph sketches. These sketches are all various restrictions of the additive pairwise spanner problem, in which one is given an undirected unweighted graph G, a set of node pairs P , and an error allowance +β, and one must construct a sparse subgraph The first part of our paper concerns pairwise distance preservers, which make the restriction β = 0 (i.e. distances must be preserved exactly). Our main result here is an upper bound of |H| = O(n 2/3 |P | 2/3 + n|P | 1/3 ) when G is undirected and unweighted. This improves on existing bounds whenever |P | = ω(n 3/4 ), and it is the first such improvement in the last ten years. We then devise a new application of distance preservers to graph clustering algorithms, and we apply this algorithm to subset spanners, which require P = S × S for some node subset S, and (standard) spanners, which require P = V × V . For both of these objects, our construction generalizes the best known bounds when the error allowance is constant, and we obtain the strongest polynomial error/sparsity tradeoff that has yet been reported (in fact, for subset spanners, ours is the first nontrivial construction that enjoys improved sparsity from a polynomial error allowance). We leave open a conjecture that O(n 2/3 |P | 2/3 + n) pairwise distance preservers are possible for undirected unweighted graphs. Resolving this conjecture in the affirmative would improve and simplify our upper bounds for all the graph sketches mentioned above. * gbodwin@stanford.edu †
For |P| = ω n 3/4 , the bound of O(n √ |P|) for pairwise preservers has very recently been improved to O(n 2/3 |P| 2/3 + n|P| 1/3 ) by Bodwin and Williams REF .
Better Distance Preservers and Additive Spanners
ArXiv
ArXiv
Mathematics Computer Science