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 themore »
Weighted Additive Spanners
A spanner of a graph G is a subgraph H that approximately preserves shortest path distances in G. Spanners are commonly applied to compress computation on metric spaces corresponding to weighted input graphs. Classic spanner constructions can seamlessly handle edge weights, so long as error is measured multiplicatively. In this work, we investigate whether one can similarly extend constructions of spanners with purely additive error to weighted graphs. These extensions are not immediate, due to a key lemma about the size of shortest path neighborhoods that fails for weighted graphs. Despite this, we recover a suitable amortized version, which lets us prove direct extensions of classic +2 and +4 unweighted spanners (both allpairs and pairwise) to +2W and +4W weighted spanners, where W is the maximum edge weight. Specifically, we show that a weighted graph G contains allpairs (pairwise) +2W and +4W weighted spanners of size O(n3/2) and O(n7/5) (O(np1/3) and O(np2/7)) respectively. For a technical reason, the +6 unweighted spanner becomes a +8W weighted spanner; closing this error gap is an interesting remaining open problem. That is, we show that G contains allpairs (pairwise) +8W weighted spanners of size O(n4/3) (O(np1/4)).
 Publication Date:
 NSFPAR ID:
 10179488
 Journal Name:
 46th International Workshop on GraphTheoretic Concepts in Computer Science (WG)
 Sponsoring Org:
 National Science Foundation
More Like this


Understanding the structure of minorfree metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a “smallcomplexity” graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minorfree metrics: 1) Construction of a light subset spanner. Given a subset of vertices called terminals, and ϵ, in polynomial time wemore »

A graph spanner is a fundamental graph structure that faithfully preserves the pairwise distances in the input graph up to a small multiplicative stretch. The common objective in the computation of spanners is to achieve the bestknown existential sizestretch tradeoff efficiently. Classical models and algorithmic analysis of graph spanners essentially assume that the algorithm can read the input graph, construct the desired spanner, and write the answer to the output tape. However, when considering massive graphs containing millions or even billions of nodes not only the input graph, but also the output spanner might be too large for a singlemore »

Given a weighted graph G(V, E) and t ≥ 1, a subgraph H is a t–spanner of G if the lengths of shortest paths in G are preserved in H up to a multiplicative factor of t. The subsetwise spanner problem aims to preserve distances in G for only a subset of the vertices. We generalize the minimumcost subsetwise spanner problem to one where vertices appear on multiple levels, which we call the multilevel graph spanner (MLGS) problem, and describe two simple heuristics. Applications of this problem include road/network building and multilevel graph visualization, especially where vertices may require differentmore »

Over the past decade, there has been increasing interest in distributed/parallel algorithms for processing largescale graphs. By now, we have quite fast algorithmsusually sublogarithmictime and often poly(łogłog n)time, or even fasterfor a number of fundamental graph problems in the massively parallel computation (MPC) model. This model is a widelyadopted theoretical abstraction of MapReduce style settings, where a number of machines communicate in an alltoall manner to process largescale data. Contributing to this line of work on MPC graph algorithms, we present poly(łog k) ε poly(łogłog n) round MPC algorithms for computing O(k^1+o(1) )spanners in the strongly sublinear regime of localmore »