The 4/3 Additive Spanner Exponent is Tight

arXiv:1511.00700v1 [] 2 Nov 2015

Amir Abboud∗ and Greg Bodwin†
Stanford University
Department of Computer Science

Abstract
A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original
graph. It is well known that there is a smooth tradeoff between the sparsity of a spanner and the quality
of its approximation, so long as distance error is measured multiplicatively. A central open question in
the field is to prove or disprove whether such a tradeoff exists also in the regime of additive error. That is,
is it true that for all ε > 0, there is a constant kε such that every graph has a spanner on O(n1+ε ) edges
that preserves its pairwise distances up to +kε ? Previous lower bounds are consistent with a positive
resolution to this question, while previous upper bounds exhibit the beginning of a tradeoff curve: all
graphs have +2 spanners on O(n3/2 ) edges [3], +4 spanners on Õ(n7/5 ) edges [13], and +6 spanners on
O(n4/3 ) edges [6]. However, progress has mysteriously halted at the n4/3 bound, and despite significant
effort from the community, the question has remained open for all 0 < ε < 1/3.
Our main result is a surprising negative resolution of the open question, even in a highly generalized
setting. We show a new information theoretic incompressibility bound: there is no mathematical function
that compresses graphs into O(n4/3−ε ) bits so that distance information can be recovered within +no(1)
error. As a special case of our theorem, we get a tight lower bound on the sparsity of additive spanners:
the +6 spanner of [6] on O(n4/3 ) edges cannot be improved in the exponent, even if any subpolynomial
amount of additive error is allowed. Our theorem implies new lower bounds for related objects as well;
for example, the twenty-year-old +4 emulator of [17] on O(n4/3 ) edges also cannot be improved in the
exponent unless the error allowance is polynomial.
Central to our construction is a new type of graph product, which we call the Obstacle Product.
Intuitively, it takes two graphs G, H and produces a new graph G ¤ H whose shortest paths structure
looks locally like H but globally like G.
∗ abboud@cs.stanford.edu
† gbodwin@cs.stanford.edu

1

Introduction

A spanner of a graph is a sparse subgraph that approximately preserves the distances of the original
graph. Spanners were introduced by Peleg and Schäffer [28] after they naturally arose in different contexts
in the late 1980s [5, 29, 4]. Today, spanners are an indispensable tool in many well-studied fields, such as
graph compression, synchronization in distributed networks, routing schemes, approximation algorithms for
all pairs shortest paths, and more.
The early results on the topic were mostly about multiplicative t-spanners, which are subgraphs that
preserve all distances up to a multiplicative constant t. A landmark upper bound result due to Awerbuch [5]
states that every graph has a multiplicative (2t − 1)-spanner on O(n1+1/t ) edges for all positive integers t.
A well-known lower bound argument shows that this tradeoff is tight under the popular Girth Conjecture of
Erdös [20]. Graphs on Ω(n1+1/t ) edges without cycles of length ≤ 2t (which exist under the conjecture) cannot
be sparsified at all without increasing a distance from 1 to 2t − 1. Therefore, the picture for multiplicative
spanners is essentially complete.
A +k additive spanner of a graph G is a subgraph H that preserves distances up to an additive constant
k, i.e. for any two nodes u, v in G we have distG (u, v) ≤ distH (u, v) + k. In most contexts, additive error is
more practically appealing than multiplicative error: a detour that adds two minutes to a trip is preferable
to one that triples its length. At first, this seemed hard to achieve; nontrivial additive spanners were only
known for special types of graphs [24, 25]. However, the seminal paper [3, 2] of Aingworth, Indyk, Chekuri,
and Motwani showed the following surprise: all graphs have +2 additive spanners on just Õ(n3/2 ) edges (see
also [17, 19, 31, 33]). In other words, the multiplicative 3-spanner shares a tight sparsity bound with the
additive +2 spanner. This result caused significant optimism in the community regarding the existence of
good additive spanners, which quickly became the central objects of study: could it be that graphs can be
sparsified to near-linear sizes while incurring only a constant additive distance error?
The 20 years that followed witnessed a high throughput of results on additive spanners (see the recent
Encyclopedia of Algorithms entry by Chechik [14]), and while this “major” [33, 15, 13, 14, 9, 10], “main”
[6, 7], “fascinating” [34], “chief open question in the field” [30] has been raised repeatedly, it has remained
inexplicably wide open.
Open Question 1. Prove or disprove: for all ε > 0, there is a constant kε such that all graphs have a +kε
additive spanner on O(n1+ε ) edges.
Open Question 1 has been generally regarded with optimism. This was motivated by some interesting
new positive results: Chechik [13] showed that all graphs have +4 spanners on Õ(n7/5 ) edges, and Baswana,
Kavitha, Mehlhorn, and Pettie [6, 7] showed that all graphs have +6 spanners on O(n4/3 ) edges (see [35, 23]
for followup work). This was also motivated by a lack of negative results: the Girth Conjecture implies an
Ω(n1+1/k ) lower bound for +(2k − 1) spanners, and the only further progress came from Woodruff [34], who
proved this lower bound unconditionally. These bounds are fully compatible with a positive resolution of
Open Question 1. Perhaps the most compelling argument for optimism, though, is the intuitive one: how
could it be that spanners enjoy improved sparsity from a +2, +4, or +6 error allowance, but then suddenly
the trail goes cold and no further tradeoffs are possible? Despite all the evidence, the edge upper bounds
have not improved beyond n4/3 for the last ten years, with no hint as to why.
Meanwhile, considerable research effort has been spent on several promising directions of attack, with
the explicit stated goal of making progress on this problem. Elkin and Peleg [19] showed that there are
near-linear size spanners with constant additive error in addition to a (1 + ε) multiplicative error (see also
[18, 33, 7] for more work on these mixed spanners). Interesting spanners with non-constant additive error have
been discovered [11, 33, 30, 7, 13, 9, 10]. Another example is the study of pairwise distance preservers and
pairwise spanners, where we only require that distances between a small set of node pairs be (approximately)
preserved [11, 15, 30, 16, 22, 27, 21, 10, 1]. While these fields have steadily progressed, none have proven
sufficient to explain or beat the n4/3 bound, and so the puzzle of Open Question 1 has endured.

Our Results
Our first result is a negative resolution of Open Question 1, and a negative resolution of the even stronger
question of the tightness of the n4/3 threshold. We prove:
2

Theorem 1. For all ε > 0, there is a δ > 0 and an infinite family of graphs G = (V, E) such that for any
subgraph H = (V, E ′ ) with |E ′ | = O(n4/3−ε ), there exist nodes u, v ∈ V with
distH (u, v) = distG (u, v) + Ω(nδ ).
Thus, the edge sparsity of n4/3 cannot be improved, even for additive error no(1) , and the +6 spanner of
Baswana et al. on O(n4/3 ) edges is essentially the sparsest possible constant error additive spanner.
Spanners are merely one (very appealing) form of graph compression. There are many other well-studied
methods of compression which do not restrict the compressed form to be a subgraph of the original graph G;
examples include Distance Oracles, Sketches, Labeling Schemes, Metric Embeddings, Emulators, etc. For
example, an emulator is a sparse weighted graph H (not necessarily a subgraph of G) that approximately
preserves the distances of G [17, 33, 34, 9].
This leads to the following information theoretic question, which is an extremely relaxed version of Open
Question 1: Does there exist a protocol for compressing a metric defined by an unweighted undirected graph
into O(n4/3−ε ) bits, for some ε > 0, such that approximate distances can be recovered up to a constant
additive error? We further generalize Theorem 1 to show that our graph family is strongly incompressible,
and provide a negative answer to this question as well.
Theorem 2. For all ε > 0, there exists a δ > 0 such that there is no mapping ψ from graphs G on n nodes
to bitstrings of length O(n4/3−ε ) such that the distances of G can always be recovered from the bitstring ψ(G)
within +nδ error.
An interesting consequence of Theorem 2 is that the 20-year-old +4 additive emulator on O(n4/3 ) edges
of Dor, Halperin, and Zwick [17] cannot be improved in the exponent even with any no(1) additive error.

The n4/3 Lower Bound

2

The goal of this section is to explicitly construct the graphs mentioned in our theorems. First, we offer
a technical overview that gives the intuition behind our construction, which will help de-mystify some steps
in our proof. We will also highlight the novelty of our approach over previous lower bound constructions.

2.1

Technical Overview

Suppose we seek a lower bound against +k spanners (think of k as a small polynomial, like n0.01 for
now). Our general approach is to start with a graph G with the following special property: there is a set of
node pairs P , with each pair at distance k, such that there is a unique shortest path in G between each pair
and the edge set of G is precisely the union of these paths. Thus, any edge deletion from G will stretch one
of the pairwise distances in P by at least +1. We then perform some transformations to G to amplify this
error. The main trick here is to pick an “obstacle graph” H, and then perform a new kind of replacement
product G ¤ H, which we call the Obstacle Product (OP). The effect will be that any spanner that deletes
too many edges from G ¤ H must increase the distance between one of the (transformed) node pairs in P
by at least +k.
Think of G as the outer graph and of H as the inner graph. The Obstacle Product G ¤ H consists of
two steps:
1. (Edge Extension) Replace every edge in G with a length k path
2. (Inner Graph Replacement) Replace each original node (i.e. not nodes created by the edge extension
step) v ∈ V (G) with a subgraph Hv that is an exact copy of H
Finally, for each edge {u, v} incident on a node v, one must choose exactly one node in Hv that will serve
as the new endpoint of this edge after the inner graph replacement step. We will temporarily skip over the
technical detail of how to choose this node. The key outcome of the OP is that the (transformed) shortest
paths for the node pairs in P must now wander through many “obstacles” Hv before reaching their final
destination.

3

Our next step is to use a counting argument to say that for a sparse enough subgraph F ⊆ G ¤ H, there
exists a (tranformed) pair in {s, t} ∈ P such that F is missing at least one of the edges used by the shortest
path ρG ¤ H (s, t) in every inner graph that this path visits. We can then prove that
distF (s, t) ≥ distG ¤ H (s, t) + k
Our proof of this claim uses two cases. Possibly (1) the shortest paths ρF (s, t) and ρG ¤ H (s, t) follow the
same path in the outer graph; that is, they intersect the same set of inner graphs in the same order. In this
case, because F is missing an edge used by ρG ¤ H (s, t) in every inner graph, ρF (s, t) must take a +1 length
detour at every inner graph, for a total error of +k. Alternately, (2) ρF (s, t) and ρG ¤ H (s, t) follow different
paths in the outer graph; that is, ρF (s, t) intersects a new inner graph. In this case, we argue that ρF (s, t)
must travel an extra k-length path in the outer graph to reach its final destination, and this is the source of
its +k error.
k
s

+1

+1

+1

Ha

Hb

Hc

t

(a) Case 1: Perhaps the new shortest path ρF (s, t) still passes through the same set of inner graphs as ρG ¤ H (s, t).
In this case, we use a counting argument to show that (for some pair (s, t)) the subgraph F is missing an edge
used by ρG ¤ H (s, t) in every inner graph that it touches. Therefore, ρF (s, t) must take a +1 edge detour in every
inner graph it touches, for a total of +k error.

s

t
Ha

Hb

Hc

k

(+0)

(b) Case 2: Perhaps the new shortest path ρF (s, t) passes through an inner graph that is not touched by the old
shortest path ρG ¤ H (s, t). In this case, we argue that ρF (s, t) must travel an extra k-length path to reach its
destination, and this is the source of its error.

Figure 1: The two possible types of new shortest paths ρF (s, t). Either one is +k longer than the original
path ρG ¤ H (s, t).

We consider the abstraction of this approach to be the biggest leap in understanding provided by our
work. The previous lower bound constructions of Woodruff [34] and Parter [27] can both be viewed within
the obstacle product framework, with the inner graph as a biclique and the outer graph as a certain type
of “layered clique.” A previous lower bound construction by the authors [1] used the same “layered clique”
outer graph, but allowed for various inner graphs to be substituted in. The construction in this paper is the
first one that allows for the modular substitution of outer graphs. Flexibility in the outer graph turns out
to be extraordinarily powerful – so much so that we are able to prove our tight spanner lower bounds while
4

only ever considering an inner graph that is a clique. With this in mind, it will simplify our paper greatly to
proceed with the restriction that H is a clique. However, we encourage the reader to keep this more general
abstraction in mind; in particular, we expect that it will be useful to consider non-clique inner graphs in
potential future work that seeks to optimize the tradeoff between δ and ε in our theorems.
Let us now return to the main construction. With the simplification that H is a clique, we will execute
the second step of the obstacle product (henceforth, the clique replacement step) as follows: replace each
node v with a clique on deg(v) nodes, and connect each of the deg(v) edges entering v to a different clique
node. Following the argument above, we now have that every subgraph F must keep at least one “clique
edge” per pair in P , or else it stretches the distance between one of these paths by +k. Assuming that no
two pairs p1 , p2 ∈ P ever use the same clique edge, this implies that any +(k − 1) additive spanner of our
graph G ¤ H must keep at least |P | edges in total. The clique edge used by a (transformed) pair p ∈ P in
a clique Hv is determined by the 2-path that the (original) path ρG (p) uses to enter and leave the node v.
Thus, our lower bound of |P | on the spanner density is realized so long as the shortest paths for every pair
of pairs in P is originally 2-path disjoint; i.e. ρG (p1 ) ∩ ρG (p2 ) does not contain any 2-paths in G.

v

v

Figure 2: If no two paths enter and leave v in the same way, then after v is replaced with a clique, all of
these paths will use a different clique edge.
We now have a lower bound on the number of edges that the spanner must keep; our next step is to
obtain a favorable upper bound on the number of nodes in the spanner. The dominant cost here is from the
edge extension step, and so the number of nodes in the spanner is roughly equal to E(G) · k. We are now
able to state the properties that we want G to have:
1. G is the union of many shortest paths between a set of node pairs P , with the following properties:
• Each pair p ∈ P has distance k
• Each pair p ∈ P has a unique shortest path between its endpoints
• These shortest paths are 2-path disjoint
Note that we want P to be as large as possible, since we will ultimately obtain a lower bound of |P |
on the number of edges in any +(k − 1) spanner.
2. G has as few edges as possible, because the number of nodes in the spanner (due to the Edge Extension
step) will be k · |E(G)|.
This completes the technical overview. In the next two subsections, we will describe how to obtain
starting graphs G with these properties in full technical detail. After that, we will repeat the details of the
obstacle product transformation more formally, and we will fully prove that this series of transformation has
the claimed properties.

2.2

Starting Point

Our starting point is the following lemma:
5

Lemma 1. For all ε > 0, there is a 0 < δ < ε, and an infinite family of graphs G = (V, E) and pair sets
P ⊆ V × V with the following properties:
1. For each pair in P , there is a unique shortest path between its endpoints
2. These paths are edge disjoint
3. For all {s, t} ∈ P , we have distG (s, t) = ∆ for some value ∆ = Θ(nδ )
4. |P | = Θ(n2−ε )
This lemma is essentially due to Coppersmith and Elkin [15], who proved a version of this lemma with
all properties except the third; it requires only a very light modification of their work to introduce the third
property. In order to make this paper self-contained, we have included a full proof of this lemma in an
appendix. Our proof is a bit different from Coppersmith and Elkin’s proof; essentially, we offer a simper
argument with a worse tradeoff between δ and ε, which will still suffice for our purposes.
An additional property of these graphs, implied by the others, is that |E| = Ω(n2−ε+δ ). This is too
dense for our purposes; for technical reasons discussed in the overview, we need a sparser object to prove
interesting results. The subject of the next lemma is to modify these graphs to reduce the edge count.

2.3

Path Compression

Our next move is to prove the following modification of Lemma 1:
Lemma 2. For all ε > 0, there is a 0 < δ < ε, and an infinite family of graphs G = (V, E) and pair sets
P ⊆ V × V with the following properties:
1. For each pair in P , there is a unique shortest path between its endpoints
2. These paths are 2-path disjoint (i.e. no two paths share any pair of consecutive edges)
3. For all {s, t} ∈ P , we have distG (s, t) = ∆ for some value ∆ = Θ(nδ )
4. |P | = Θ(n2−ε )
5. |E| = O(n3/2 )
There are two important differences between Lemmas 1 and 2: the paths have become 2-path disjoint
rather than edge disjoint, and the edge count has fallen from ≈ n2 to ≈ n3/2 . For this reason, we think of
this step as path compression, as we are essentially packing the same number of shortest paths into many
fewer edges while only slightly relaxing the paths’ overlap properties.
We will prove this lemma by starting with a graph as described in Lemma 1, and performing a transformation to this graph to give it the properties of Lemma 2. With this in mind, one should not think of the
parameters n, ε, δ in Lemma 2 as the same as those in Lemma 1; despite having the same names, they will
change across the transformation.
We will now describe our transformation at a high level. Start with a graph G = (V, E) and pair set
P ⊆ V × V as described in Lemma 1. Our goal is to create a new graph G′ = (V ′ , E ′ ) and pair set
P ′ ⊆ V ′ × V ′ as described in Lemma 2. We achieve this by defining G′ to be a product of G1 and G2
(which are two identical copies of G), and we define P ′ to be a product of P1 and P2 (which are two identical
copies of P , although P1 contains node pairs from G1 and P2 contains node pairs from G2 ). Intuitively,
a new pair (p1 , p2 ) ∈ P ′ means that the pair p1 must be traversed in the graph G1 , and the pair p2 must
be simultaneously traversed in the graph G2 . We then carefully design the new edge set such that an edge
in E ′ corresponds to a step in G1 or a step in G2 (but not both), and the shortest paths for P ′ will take
alternating steps in G1 and G2 .
From this, we can argue 2-path disjointness of the shortest paths for P ′ as follows. Consider a length 2
subpath of the shortest path for some pair p′ ∈ P ′ . These two edges correspond to a step in G1 and a step
in G2 ; since shortest paths for P1 in G1 are completely edge disjoint (and the same for P2 , G2 ), these edges
uniquely determine pairs p1 ∈ P1 and p2 ∈ P2 . Therefore, this information is sufficient to uniquely determine
the new pair p′ = (p1 , p2 ) being considered.
We will now describe this construction in full detail.
6

• The nodes: For each (possibly non-distinct) pair of nodes u1 , u2 ∈ V and index i ∈ {1, 2} we add the
triple (u1 , u2 , i) as a new node to G′ . That is, the node set of our new graph G′ will be defined as:
V ′ = {(u1 , u2 , i) | u1 , u2 ∈ V, i ∈ {1, 2}} .
Semantically, the index i dictates whether we are supposed to take a step in the graph G1 (represented
by the first coordinate) or the graph G2 (represented by the second coordinate).
• The edges: To define the edges of G′ we first need to define a forwards direction for each edge in E.
These directions will be chosen so that the shortest path between any pair {s, t} ∈ P can be thought
of as a walk that only traverses edges in their forwards direction. We do this by fixing an arbitrary
ordering s
t for every pair {s, t} ∈ P , and then directing the edges of the unique shortest path
between this pair from s towards t. In other words, for any edge {u, v} on the path, we define the
→

u → v direction to be forward iff v is closer to t than it is to s. Let P be the version of P with
→

an arbitrary ordering imposed on each pair, and let E be the version of E with an (ordered) edge
(u, v) ∈ E corresponding to each (unordered) edge {u, v} ∈ E if u → v was defined as the forwards
direction. A crucial observation here is that the forwards direction is well-defined and consistent for
all the edges in E, due to the property that every edge in E is on the shortest path for exactly one
pair in P .
We are now ready to define the edge set E ′ of G′ . The edges will be defined differently depending
on the index value i of the node. For every node x = (u1 , u2 , 1) ∈ V ′ , we add an edge {x, y} to G′
→

if and only if y = (u′1 , u2 , 2) and (u1 , u′1 ) ∈ E. Additionally, for every node x = (u1 , u2 , 2) ∈ V ′ , we
→

add an edge {x, y} to G′ if and only if y = (u1 , u′2 , 1) and (u2 , u′2 ) ∈ E. Intuitively, this enforces that
any interesting shortest path must alternate between taking a forwards step in the first coorinate, and
then a forwards step in the second coordinate. More formally, the edge set of our new graph is:


→
E ′ = {(u1 , u2 , 1), (u′1 , u2 , 2)} | (u1 , u′1 ) ∈ E, u2 ∈ V


→
∪ {(u1 , u2 , 2), (u1 , u′2 , 1)} | (u2 , u′2 ) ∈ E, u1 ∈ V .
• The pair set: Our new pair set P ′ will be composed of pairs of old pairs from P , and its definition
will rely on the ordering of each pair that we fixed above. For each ordered, possibly non-distinct
→

pair of pairs (s1 , t1 ), (s2 , t2 ) ∈ P , we add the pair {(s1 , s2 , 1), (t1 , t2 , 1)} to P ′ . Intuitively, given pairs
→

p1 , p2 ∈ P , the corresponding new pair dictates that p1 must be traveled in G1 and p2 must be traveled
in G2 . The formal definition of P ′ is:


→
P ′ = {(s1 , s2 , 1), (t1 , t2 , 1)} | (s1 , t1 ), (s2 , t2 ) ∈ P .
In order to prove Lemma 2, we will first define a path for each pair in P ′ that alternates between taking
a step in G1 and a step in G2 as described above.
Definition 1 (The path ρ). We define
ρ({(s1 , s2 , 1), (t1 , t2 , 1)}) := (u1 = (s1 , s2 , 1), u2 , . . . , uk−1 , uk = (t1 , t2 , 1))
where
1
2
1. ui for odd i is equal to (v⌈i/2⌉
, v⌈i/2⌉
, 1), and
1
2
2. ui for even i is equal to (vi/2+1
, vi/2
, 2)

where vj1 is the j th node on the unique shortest path between s1 and t1 in G, and vj2 is the j th node on the
unique shortest path between s2 and t2 in G.
7

In other words, ρ(p′ ) is built iteratively by alternatingly changing the first coordinate along the unique
shortest path from s1 to t1 in G, and then changing the second coordinate along the unique shortest path
from s2 to t2 in G. To see that the ρ(p′ ) is well defined for all p′ ∈ P ′ (i.e. the path ρ(p′ ) exists in G′ ),
1
2
1
2
note that by construction an edge from (v⌈i/2⌉
, v⌈i/2⌉
, 1) to (v⌈i/2⌉+1
, v⌈i/2⌉
, 2) (for odd i) exists iff the edge
→

→

1
1
(v⌈i/2⌉
, v⌈i/2⌉+1
) is in E, which follows from the fact that (s1 , t1 ) ∈ P . The other case, where i is even,
follows from an entirely symmetric argument.
Also note that the length of ρ(p′ ) is exactly 2∆ for all p′ ∈ P ′ . Our next step is to argue that ρ(p′ ) is
the unique shortest path between its endpoints.

Claim 1. For all pairs p′ ∈ P ′ , the path ρ(p′ ) is the unique shortest path between the endpoints of p′ .
Proof. Let τ (p′ ) be a shortest path between the endpoints of p′ for some p′ = {s′ , t′ } ∈ P ′ , where s′ =
(s1 , s2 , 1) and t′ = (t1 , t2 , 1). We will show that τ (p′ ) must be equal to ρ(p′ ).
Any path in G′ can be seen as a combination of a path in G1 and a path in G2 . Let τ1 be the walk in
G defined by the sequence of nodes taken by the first coordinate of the nodes in τ (p′ ), ignoring consecutive
repeats, and let τ2 be the walk in G defined by the sequence of nodes taken by the second coordinate of the
nodes in τ (p′ ), again ignoring consecutive repeats.
By definition of G′ we have that τ1 is a path in G from s1 to t1 , while τ2 is a path in G from s2 to
t2 . Since any edge in G′ changes only one of the two coordinates, we have that |τ (p′ )| = |τ1 | + |τ2 |. Since
|τ1 |, |τ2 | ≥ ∆, we have that |τ (p′ )| ≥ 2∆, with equality only if |τ1 | = |τ2 | = ∆ and so τ1 , τ2 are the respective
→

unique shortest paths between (s1 , t1 ), (s2 , t2 ) ∈ P . Therefore, we conclude that τ (p′ ) and ρ(p′ ) must take
the exact same steps τ1 through G1 and τ2 through G2 . To finish the proof, we will argue that they take
their steps in the same order.
Assume towards a contradiction that τ (p′ ) and ρ(p′ ) differ, and let (x, y, 1) be the first node on which
they diverge (the case (x, y, 2) is symmetric), so that ρ(p′ ) takes an edge to (x′ , y, 2) but τ (p′ ) takes an edge
to some other node (x∗ , y ∗ , 2). There are now two possible cases:
The first case is that x∗ 6= x and y ∗ = y. Then by construction the corresponding step from x to x∗
→

taken by τ1 is in the forward direction (i.e. (x, x∗ ) ∈ E). However, since (x′ , y, 2) and (x∗ , y ∗ , 2) are distinct
nodes, we have x∗ 6= x′ . Since x′ is the unique continuation of the shortest path from s1 to t1 , it follows that
τ1 is not the shortest path from s1 to t1 , which is a contradiction.
The second case is that x∗ = x and y ∗ 6= y. Then by construction of our edge set, the corresponding step
→

from y to y ∗ taken by τ2 is in the backwards direction (i.e. (y, y ∗ ) ∈
/ E). By construction, the shortest walk
from s2 to t2 only traverses edges in their forwards direction. Thus, τ2 is not the shortest path from s2 to
t2 , which is a contradiction.
We have now shown that τ (p′ ) = ρ(p′ ), and thus, ρ(p′ ) is the unique shortest path in G′ between its
endpoints.
Finally, we observe that, from our construction, the paths ρ(p′ ), ρ(p′′ ) are 2-path disjoint for any distinct
p , p′′ ∈ P ′ .
′

Claim 2. For any two distinct pairs p′ 6= p′′ ∈ P ′ , the paths ρ(p′ ), ρ(p′′ ) are 2-path disjoint.
Proof. Consider two pairs p′ = {(s′1 , s′2 , 1), (t′1 , t′2 , 1)} ∈ P ′ and p′′ = {(s′′1 , s′′2 , 1), (t′′1 , t′′2 , 1)} ∈ P ′ for which
there is a 2-path (a, b, c) that is a subpath of both ρ(p′ ) and ρ(p′′ ). We will show that p′ and p′′ must be the
same pair.
By definition of ρ, the subpath (a, b, c) must have one of two forms: either a = (x1 , y2 , 1), b = (x′1 , y2 , 2), c =
′
(x1 , y2′ , 1), or a = (x1 , y2 , 2), b = (x1 , y2′ , 1), c = (x′1 , y2′ , 2). Assume we are in the first case, and the second
→

case is symmetric. Again by the definition of ρ, we must have that (x1 , x′1 ) ∈ E is on the unique (s′1 , t′1 )
shortest path and on the unique (s′′1 , t′′1 ) shortest path in G. Since the shortest paths between pairs in P
→

are edge disjoint in G, this implies that (s′1 , t′1 ) = (s′′1 , t′′1 ). Moreover, we have that (y2 , y2′ ) ∈ E is on the
unique shortest paths for both (s′2 , t′2 ) and (s′′2 , t′′2 ), and so we also have that (s′2 , t′2 ) = (s′′2 , t′′2 ). Together,
these imply that p′ = p′′ .
We can now prove Lemma 2:
8

Proof of Lemma 2. It is immediate from the construction that N := |V ′ | = Θ(n2 ), and that |P ′ | = |P |2 =
Θ(n4−2ε ) = Θ(N 2−ε ) (thus, the new value of ε is the same as the old value of ε used to create G via Lemma
1). Additionally, a loose (but sufficient for our purposes) upper bound on |E ′ | follows from the observation
that each node can have at most 2n neighbors, and thus |E ′ | = O(n3 ) = O(N 3/2 ).
We have demonstrated above that ρ(p′ ) is the unique shortest path for any pair p′ ∈ P ′ , and that ρ(p′1 )
and ρ(p′2 ) are 2-path disjoint for any p′1 6= p′2 ∈ P ′ . We additionally have |ρ(p′ )| = 2∆ = Θ(nδ ) = Θ(N δ/2 )
(and so the new value of δ is half the old value of δ used to create G via Lemma 1). Since the values of ε, δ
used to create G satisfied 0 < δ < ε, and our new value of ε has remained unchanged while our new value of
δ has been halved, we then still have 0 < δ < ε.

2.4

The Obstacle Product

Our final move is to produce an Obstacle Product (OP) G ¤ K, where G is a graph produced by Lemma
2, and K is a clique. For intuition on the obstacle product and why it is useful, we refer the reader to
the overview at the beginning of this section. Its ultimate purpose is to prove our main theorem, which we
restate below for convenience:
Theorem 1. For all ε > 0, there is a δ > 0 and an infinite family of graphs G = (V, E) such that for any
subgraph H = (V, E ′ ) with |E ′ | = O(n4/3−ε ), there exist nodes u, v ∈ V with
distH (u, v) = distG (u, v) + Ω(nδ ).
Let us now fix an ε > 0. Our next steps will be to choose an appropriate G, K, describe how to build
the obstacle product G ¤ K, and then argue that this is sufficient to prove Theorem 1.
Starting Graph. We start by applying Lemma 2 with parameter α = ε/2, to obtain a graph G = (V, E)
on |V | = n nodes, |E| = O(n3/2 ) edges, and a pair set P ⊆ V × V of size |P | = Θ(n2−α ) such that: the
distance between any pair {s, t} ∈ P is exactly ∆, for some ∆ = Θ(nβ ) and 0 < β < α (which implies
0 < β < ε/2), and the shortest paths between pairs in P are 2-path disjoint.
We next take the OP of G with a clique K. This OP consists of the following two transformations:
OP – Edge Extension. First, we replace every edge in G with a path of length ℓ = 3∆.
More formally, if the edge e = {u, v} ∈ E, then we add the nodes (e, 1), . . . , (e, ℓ) to V ′ and add the edges
{u, (e, 1)}, {v, (e, ℓ)}, and {(e, i), (e, i + 1)} for all i ∈ [ℓ − 1] to E ′ . The choice of which endpoint (e, 1) or
(e, ℓ) we connect to u or v is arbitrary.
Note that the total number of nodes in G′ after this transformation is O(n3/2+β ).
OP – Clique Replacement. Next, for each original node v ∈ V (i.e. not nodes introduced by the edge
extension step), we replace v with a clique on degG (v) nodes, with each incoming edge connected to a unique
node in the new clique.
More formally, let I(v) ⊆ E be the set of edges incident to v ∈ V , and introduce a new node (v, e) for
each edge e ∈ I(v). These new nodes will be connected in a clique: for each ei , ej ∈ I(v) we add the edge
{(v, ei ), (v, ej )} to E ′ . The clique that replaces a node v will be denoted Kv . We will call an edge contained
in one of these cliques a clique edge. After this replacement, each node (v, e) will still be attached to an
endpoint of the path corresponding to the edge e, i.e. we will have an edge {(v, e), (e, α)} where α ∈ {1, ℓ}
depends on the (arbitrary) ordering we chose in the edge-extension step. P
The number of nodes added in this clique-replacement step is exactly v∈V degG (v) = 2|E|, which is
O(n3/2 ). An important feature of this step is that we have introduced many new edges to G′ ; we will implicitly discuss this in the proof of correctness.
Let k = ∆ − 1 = Θ(nβ ). To complete the proof, we will argue that any subgraph of G′ with fewer than
O(n2−α ) edges must distort the distances by more than +k.

9

Proof of Correctness. First, we will build a pair set P ′ ⊆ V ′ × V ′ ; to prove Theorem 1 it will be sufficient
to only consider node pairs in P ′ . For each pair {s, t} ∈ P , let the nodes on the unique (s, t)-shortest path
in G be s = u0 → u1 → · · · → u∆−1 → u∆ = t, and let the ∆ edges on this path be denoted ei = {ui−1 , ui }
for all i ∈ [∆] (these definitions use the feature of Lemma 2 that all pairs in P are at distance exactly ∆ in
G). Consider the nodes s′ = (s, e1 ), t′ = (t, e∆ ) ∈ V ′ , and add {s′ , t′ } as a pair to P ′ .
We will next reason about the structure of the shortest path between s′ and t′ in G′ . The following (s′ , t′ )
path will exist by construction: Starting from s′ = (s1 , e1 ), walk the path in G′ that replaced the edge e1
in G, reaching the node (u1 , e1 ). Then, walk the clique edge {(u1 , e1 ), (u1 , e2 )}, which we will denote by es,t
1
since it is the first clique edge on the (s′ , t′ )-path. Then, similarly, walk the path that replaced to the edge
e2 , and then walk the clique edge {(u2 , e2 ), (u2 , e3 )}, and so on until we reach t′ . This walk will traverse each
of the ℓ-length paths that replaced our edges ei (as well as some clique edges). The ith clique edge crossed
′
will be es,t
i = {(ui , ei ), (ui , ei+1 )}, for i ∈ [∆ − 1]. Thus, this walk will reach the node t = (t, e∆ ) after it has
taken exactly ∆ paths of length ℓ, plus (∆ − 1) clique edges, i.e. D := ∆ · ℓ + (∆ − 1) edges in total. Let
ρ(s′ , t′ ) be the path in G′ defined by this walk, and let C s,t be the set of clique edges on this path.
The following claim is an integral part of our proof:
Claim 3. For any two distinct pairs {s1 , t1 } 6= {s2 , t2 } ∈ P , the corresponding clique edge sets C s1 ,t1 , C s2 ,t2
are disjoint.
Proof. Assume towards a contradiction that C s1 ,t1 , C s2 ,t2 share a clique edge {(u, ei ), (u, ej )} for some u ∈ V
and ei , ej ∈ IG (v). This implies that the 2-path in G composed of ei and ej is a subpath of the unique
shortest (s1 , t1 )-path in G and of the unique shortest path (s2 , t2 )-path. By Lemma 2 this can only happen
if {s1 , t1 } = {s2 , t2 }, which is a contradiction.
Next, we examine the structure of alternate short paths between s and t.
Claim 4. Let {s, t} be a pair in P , let {s′ , t′ } be the corresponding pair in P ′ , and let ρ′ (s′ , t′ ) be a (not
necessarily shortest) (s′ , t′ ) path of length less than D + ∆. Let K = (Ks , Kv1 , . . . , Kvx−1 , Kt ) be the sequence
′
of cliques created in the Clique Replacement step that intersect ρ(s′ , t′ ), and let K′ = (Ks , Kv1′ , . . . , Kvx−1
, Kt )
be the sequence of cliques that intersect ρ′ (s′ , t′ ). Then K = K′ .
Proof. Note that, by construction, the node sequence (s, v1 , . . . , v∆−1 , t) is then the unique shortest (s, t)
′
path in G. Similarly, note that the node sequence (s, v1′ , . . . , vx−1
, t) is an (s, t) path in G. If these node
sequences are identical, then the claim holds. Assume towards a contradiction that the node sequences differ.
Then the latter sequence must be at least one element longer than the former sequence (i.e. x > ∆). Both
ρ(s′ , t′ ) and ρ′ (s′ , t′ ) must travel a path of length ℓ between any two cliques, and so the number of path edges
traveled by ρ′ (s′ , t′ ) is at least ℓ = 3∆ more than the number of path edges traveled by ρ(s′ , t′ ). Meanwhile,
ρ(s′ , t′ ) walks exactly ∆ clique edges, while ρ′ (s′ , t′ ) walks exactly x clique edges. Since x ≥ ∆, this implies
that the total length of ρ′ (s′ , t′ ) is at least +3∆ longer than ρ(s′ , t′ ). This is a contradiction, and so it must
be the case that the original node sequences are equal, and so K = K′ .
This lets us prove the next claim, which is the key to lower bounding the number of edges in any additive
+k spanner (recall that we chose k = ∆ − 1).
Claim 5. For any pair {s, t} ∈ P , any path of length less than D + k from s′ to t′ must use at least one of
the clique edges C s,t .
Proof. Let ρ′ (s′ , t′ ) be a path from s′ to t′ of length less than D + k. By Claim 4, we know that ρ′ (s′ , t′ )
must pass through exactly the same cliques in the same order as ρ(s′ , t′ ), which implies that it must walk
exactly the same set of paths introduced in the Edge Extension step of the OP. This implies that for all
i ∈ [∆], ρ′ (s′ , t′ ) contains a path from (ui , ei ) to (ui , ei+1 ) as a subpath. Let the length of this subpath be
s,t
di for some di ≥ 1, and note that di = 1 if and only if ρ′ (s′ , t′ ) uses the clique edge es,t
i ∈ C . A direct
′ ′ ′
calculation shows that the length of ρ (s , t ) is equal to
ℓ(∆ − 1) +

∆−1
X

di = D +

∆−1
X

(di − 1)

i=1

i=1

10

If di > 1 for all i, then this is equal to at least D + (∆ − 1) = D + k, which contradicts the assumption
that ρ′ (s′ , t′ ) has length less than D + k. Thus, di = 1 for some i, and so ρ′ (s′ , t′ ) uses the clique edge
{(ui , ei ), (ui , ei+1 )}.
We can now prove our main theorem from a direct counting argument. Recall that our graph G′ has
N = O(n3/2+β ) nodes, and that our pair set P ′ is of size |P ′ | = Θ(n2−α ). Assume towards a contradiction
4
3
that there is a subgraph H = (V ′ , EH ) of G′ on |EH | = O(N 4/3−ε ) = O(n(3/2+β)(4/3−ε) ) = O(n2+ 3 β− 2 ε−εβ )
′ ′
′
′
edges in which for all pairs {s , t } ∈ P the distance in H is no more than the distance in G plus k, i.e. at
most D + k. By Claim 5, for each such pair {s′ , t′ } ∈ P ′ at least one of the clique edges in C s,t must exist
in H, and from Claim 3 we know that all these edges are distinct. Therefore, EH must contain at least one
distinct edge per pair in P ′ , for a total of |EH | = Ω(n2−α ) edges. These two bounds on |EH | imply that:
4
3
2 − α ≤ 2 + β − ε − εβ
3
2


4
3
+β ε≤α+ β
2
3
We additionally know that 0 < β < α ≤ ε/2. We complete the proof by arguing that there is no possible
setting of α, β that makes these inequalities hold simultaneously, and so we have a contradiction and the
subgraph H cannot exist. To see this, we will substitute β = 0 into the left hand side of the inequality (giving
the left hand side of the inequality its lowest conceivable value), and simultaneously substitute α = β = 2ε
into the right hand side of the inequality (giving the right hand side of the inequality its highest conceivable
value). We obtain:


ε 4 ε
3
+0 ε≤ + ·
2
2 3 2
7
3
·ε≤ ·ε
2
6
which contradicts the fact that ε > 0. This implies Theorem 1 with parameter δ set to β (since k = Ω(nβ )).

2.5

Strong Incompressibility

Finally, we provide some additional observations about our construction to prove our strong incompressibility results. We will prove:
Theorem 2. For all ε > 0, there exists a δ > 0 such that there is no mapping ψ from graphs G on n nodes
to bitstrings of length O(n4/3−ε ) such that the distances of G can always be recovered from the bitstring ψ(G)
within +nδ error.
Our argument proceeds along the lines of the well known proof that the Girth Conjecture implies that
graphs cannot be compressed into o(n1+1/t ) bits without incurring a multiplicative error of (2t − 1) [32],
which is based on the works of Matoušek [26] and Bourgain [12].
For any subset of pairs T ⊆ P ′ , we define GT = (V, ET ) to be the subgraph of G obtained by removing
′ ′
′
all clique edges C s ,t corresponding to all pairs {s′ , t′ } in T . Note that there are 2|P | such subgraphs GT .
Claim 6. For all T ⊆ P ′ and {s′ , t′ } ∈ P ′ \ T we have that distGT (s′ , t′ ) ≤ D.
Proof. The only edges that are missing from GT are clique edges corresponding to pairs in T . By Claim
′ ′
3, none of these clique edges are in C s ,t for any pair {s′ , t′ } ∈
/ T . Therefore, the length D path ρ(s′ , t′ )
remains in GT .
Claim 7. For all T ⊆ P ′ and {s′ , t′ } ∈ T we have that distGT (s′ , t′ ) > D + k.
Proof. Any path from s′ to t′ in GT cannot use any of the clique edges in C s,t . By Claim 5, the length of
such path cannot be ≤ D + k.
11

′

4/3−ε′

)
The above two claims show that there exists a set G of 2|P | = 2Θ(N
graphs (which are GT for each
′
′
possible pair subset T ⊆ P ) on the same node set V of size N , as well as a pair set P ′ ⊆ V ′ × V ′ of size
′
|P ′ | = Θ(n4/3−ε ) (for some ε′ > 0), such that the following condition is true:
For any two graphs G1 , G2 ∈ G there is a pair of nodes {s′ , t′ } ∈ P ′ for which

| distG1 (s′ , t′ ) − distG2 (s′ , t′ )| ≥ k
where k = Ω(N δ ). This means that for any compression function ψ that takes a graph G on n nodes and
produces a bitstring of length less than |P |, there exist two different graphs G1 , G2 ∈ G that map to the
same bitstring. Thus, when the distance between s′ and t′ is recovered from this bitstring, it will be at least
±Ω(nδ ) from the correct value for either G1 or G2 . Therefore, no such compression function can output
′
bitstrings of length O(n4/3−ε ) such that distances can be recovered within +O(nδ ) error.

3

Conclusion

Our work shows that graphs cannot be compressed into O(n4/3−ε ) bits while maintaining distances within
a constant (or even subpolynomial) additive error. We thus implicitly show that the 4/3 exponent is tight for
additive spanners and emulators, and unbeatable for any other notion of graph compression where distance
error is measured additively. We consider it particularly interesting that the analogous statement is false
for multiplicative error; that is, many graph compression schemes are capable of obtaining near-linear sized
compression with only a constant multiplicative distance error.
Our main technical contribution is the Obstacle Product, which seems to be a powerful framework for
generating families of graphs that are hard to efficiently sketch while approximately maintaining distances.
Below, we mention some open questions from the realm of spanners that are left open after this work, and
for which our framework could be applicable.
Completing the picture of constant error additive spanners. The only remaining gap (in the
exponent) in our understanding of constant error additive spanners is the +4 error case. The lower bounds
allow for the possibility of +4 spanners on O(n4/3 ) edges, while upper bounds have only realized Õ(n7/5 )
[13]. Note that this gap does not exists for emulators. Closing this gap is perhaps the most natural and
intriguing open question that remains.
Our work also leaves no(1) gaps between upper and lower bounds. Do all graphs have +k spanners on
O(n4/3 / log n) edges, or maybe even O(n4/3 / logk n)? Our current construction allows this; with a finergrained analysis of the rate at which
√ δ and ε approach 0, we can show that our graphs lack spanners of any
constant additive error on n4/3 /2ω( log n) edges. It would be interesting to close this gap.
Other Kinds of Spanners. We have shown that +Ω(nδ ) additive error is required for spanners on
O(n4/3−ε ) edges. It is then natural to ask precisely how much polynomial error is required for sparse
spanners; for example, what is the smallest constant δ such that all graphs have +O(nδ ) spanners of nearly
linear size? The current best upper bound on δ is 37 , due to [10]. An extremely naı̈ve application of our
framework, with no more tricks than those explicitly mentioned in this paper, suffices to proves that δ is at
1
. Finding the exact tradeoff between the error parameter nδ and the sparsity n4/3−ε is still open.
least 21
Related notions are sublinear error spanners, where if the original distance is d it must be preserved up to
d + o(d), and (α, β) mixed spanners, where even (1 + α) · d + β is allowed. Can our framework be adapted to
obtain tight lower bounds in these settings as well? Finally, it would be interesting to understand the exact
tradeoff for pairwise spanners [16, 15, 22, 21]. Both of our main results hold even if only the distances within
a pair set of size Θ(n4/3 ) need to be preserved. When only smaller pair sets are considered, it is known that
one can obtain +6 spanners on O(n4/3−ε ) edges [21], although the exact nature of the tradeoff between pair
set size, error, and sparsity remains open.
Pairwise Distance Preserver Lower Bounds. Perhaps the most promising way to solve some of the
above problems is by improving the δ, ε tradeoff in the original graphs from our first lemma. These graphs
are called pairwise distance preserver lower bounds, and there is currently a sizeable knowledge gap regarding

12

√

their optimal sparsity [15, 10]. In particular, it is known that for any |P | = n2 /2ω( log n) we can construct
a graph G and pair set P such that the pairs in P have unique edge-disjoint shortest paths of length ω(1)
(see [15], or the construction in Appendix
3). Through our obstacle product construction, this statement
√
directly translates into the n4/3 /2O( log n) lower bound against constant error additive spanners mentioned
above. This leads to the following interesting open question: can one improve the bound on |P | in the above
statement all the way up to o(n2 )? If so, it would imply the very interesting statement that constant error
spanners on o(n4/3 ) edges are not possible in general.

Acknowledgements
We are grateful to Virginia Vassilevska Williams for her sustained advice throughout this project, and to
Seth Pettie and Ryan Williams for advice on an earlier draft of this paper that has considerably improved
its presentation.
This work was supported by NSF Grants CCF-1417238, CCF-1528078 and CCF-1514339, and BSF Grant
BSF:2012338. This work was done in part while the authors were visiting the Simons Institute for the Theory
of Computing.

References
[1] Amir Abboud and Greg Bodwin. Error Amplification for Pairwise Spanner Lower Bounds. In Proc. of
27th SODA, to appear, 2016.
[2] Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter
and shortest paths (without matrix multiplication). SIAM J. Comput., 28:1167–1181, 1999.
[3] Donald Aingworth, Chandra Chekuri, and Rajeev Motwani. Fast Estimation of Diameter and Shortest
Paths (without Matrix Multiplication). In Proc. of 7th SODA., pages 547–553, 1996.
[4] I Althöfer, G Das, D Dobkin, D Joseph, and J Soares. On sparse spanners of weighted graphs. Discrete
& Computational Geometry, 9:81–100, 1993.
[5] Baruch Awerbuch. Complexity of network synchronization. Journal of the ACM, pages 32,804–823,
1985.
[6] Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. New constructions of (α,
β)-spanners and purely additive spanners. In Proc. of 16th SODA, pages 672–681, 2005.
[7] Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. Additive spanners and (α,
β)-spanners. ACM Transactions on Algorithms, 7(1):5, 2010.
[8] Felix A Behrend. On sets of integers which contain no three terms in arithmetical progression. Proceedings of the National Academy of Sciences of the United States of America, 32(12):331, 1946.
[9] Greg Bodwin and Virginia Vassilevska Williams. Very Sparse Additive Spanners and Emulators. In
Proc. of 6th ITCS, pages 377–382, 2015.
[10] Greg Bodwin and Virginia Vassilevska Williams. Better Distance Preservers and Additive Spanners. In
Proc. of 27th SODA, to appear, 2016.
[11] Béla Bollobás, Don Coppersmith, and Michael Elkin. Sparse distance preservers and additive spanners.
In Proc. of 14th SODA, pages 414–423, 2003.
[12] Jean Bourgain. On lipschitz embedding of finite metric spaces in hilbert space. Israel Journal of
Mathematics, 52(1-2):46–52, 1985.
[13] Shiri Chechik. New Additive Spanners. In Proc. of 24th SODA, pages 498–512, 2013.
[14] Shiri Chechik. Additive Spanners. In Encyclopedia of Algorithms. 2014.
13

[15] Don Coppersmith and Michael Elkin. Sparse Sourcewise and Pairwise Distance Preservers. SIAM
Journal on Discrete Mathematics, pages 463–501, 2006.
[16] Marek Cygan, Fabrizio Grandoni, and Telikepalli Kavitha. On Pairwise Spanners. In Proc. of 30th
STACS, pages 209–220, 2013.
[17] Dorit Dor, Shay Halperin, and Uri Zwick. All Pairs Almost Shortest Paths. In Proc. of 37th FOCS,
pages 452–461, 1996.
[18] Michael Elkin. Computing almost shortest paths. ACM Trans. Algorithms, pages 1(2):283–323, 2005.
[19] Michael Elkin and David Peleg. (1 + ǫ, β)-spanner constructions for general graphs. SIAM J. Comput.,
33(3):608–631, 2004.
[20] Paul Erdös. Extremal problems in graph theory. Theory of graphs and its applications, pages 29–36,
1964.
[21] Telikepalli Kavitha. New Pairwise Spanners. In Proc. of 32nd STACS, pages 513–526, 2015.
[22] Telikepalli Kavitha and Nithin Varma. Small Stretch Pairwise Spanners. In Proc. of 40th ICALP, pages
601–612, 2013.
[23] Mathias Bæk Tejs Knudsen. Additive spanners: A simple construction. In Proc. of 14th SWAT, pages
277–281, 2014.
[24] Arthur L. Liestman and Thomas C. Shermer. Additive spanners for hypercubes. Parallel Processing
Letters, 1(01):35–42, 1991.
[25] Arthur L. Liestman and Thomas C. Shermer. Additive graph spanners. Networks, 23(4):343–363, 1993.
[26] Jiřı́ Matoušek. On the distortion required for embedding finite metric spaces into normed spaces. Israel
Journal of Mathematics, 93(1):333–344, 1996.
[27] Merav Parter. Bypassing Erdös’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners. In Proc.
of 41st ICALP, pages 608–619, 2014.
[28] David Peleg and Alejandro Schaffer. Graph spanners. Journal of Graph Theory, pages 13:99–116, 1989.
[29] David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypercube. SIAM Journal of
Computing, pages 18,740–747, 1989.
[30] Seth Pettie. Low distortion spanners. ACM Transactions on Algorithms, 6(1), 2009.
[31] Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic Constructions of Approximate Distance
Oracles and Spanners. In Proc. of 32nd ICALP, pages 261–272, 2005.
[32] Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM, 52(1):1–24, 2005.
[33] Mikkel Thorup and Uri Zwick. Spanners and emulators with sublinear distance errors. In Proc. of 17th
SODA, pages 802–809, 2006.
[34] David P. Woodruff. Lower bounds for additive spanners, emulators, and more. In Proc. of 47th FOCS,
pages 389–398, 2006.
[35] David P. Woodruff. Additive Spanners in Nearly Quadratic Time. In Proc. of 37th ICALP, pages
463–474, 2010.

14

A

Graphs with many long edge-disjoint shortest paths

In this section we provide a proof of Lemma 1 which is the starting point for our lower bound constructions.
One way to prove the Lemma is by simple modifications to the constructions of Coppersmith and Elkin [15]
for pairwise distance preserver lower bounds. Their construction relied on lemmas from discrete geometry
regarding the size of the convex hull of points in a radius r ball in the d-dimensional integer lattice. We will
provide a simpler proof of this lemma (our proof is less efficient in the tradeoff between ε and δ, but will
suffice for our purposes). Our proof relies on generalizations of the well-known arithmetic progression free
sets that have found countless applications in combinatorics and theoretical computer science.
k-Average-Free Sets. We say that a set of integers S ⊆ [N ] is k-Average-Free if, for any collection of k
integers x1 , . . . , xk ∈ S that are not all equal, we have
k
X

xi 6= k · x̄

i=1

for all x̄ ∈ S. In other words, S does not contain the arithmetic mean of any k of its elements, except for
the trivial case when all of these elements are equal. An adaptation of a construction by Behrend [8] proves
the existence of k-average-free sets with surprisingly large density:
Lemma 3. For all ε > 0 there is a δ > 0 such that for infinitely many integers N there exist k-average-free
sets of size Θ(N 1−ε ), with k = Ω(N δ ).
Proof. Fix ε > 0, and let d = ⌈3/ε⌉ ∈ N and δ = 1/(2d2 ) > 0. Let p be a parameter that can take any value
in N; we will construct a k-average-free set A ⊆ [N ] where k, N, and |A| are functions of p.
Let X = [p]d be the set of all d-dimensional vectors whose coordinates are integers in [p]. For any
r ∈ [dp2 ], let
Xr := {x ∈ X | kxk22 = r}
i.e. Xr is the set of vectors for which the square of the Euclidian norm is r. Observe that for all x ∈ X we
have
1 ≤ kxk22 ≤ dp2
and so the sets X1 , . . . , Xdp2 form a partition of the set X. Let V = Xr be the largest of these sets. Since
|X| = pd , we have that
pd
pd−2
|V | ≥ 2 =
.
dp
d
We now claim that the set V is the analogue of a vector-valued “k-average-free set” for any k ∈ N, in the
sense that the average of any set of vectors (not all equal) in V is not an element of V . This follows simply
from the fact that all vectors in V have the same Euclidian norm, and so they form a convex set in Rd .
Our next step is to convert the vector set V into an integer set A in a way that preservers summation.
We remark that this step is not strictly necessary; i.e. it would be possible to prove Lemma 1 using only
a vector-valued average free set. However, it will simplify the proofs that follow to consider integers rather
than vectors. Our transformation will be defined by the function f : [p]d → [N ], where N = ((k + 1)p)d , in
which for any vector v = (v1 , . . . , vd ) ∈ [p]d we interpret v1 , . . . , vd as the digits of a number in base (k + 1)p.
More formally, we define
f (v) := v1 · q 0 + v2 · q 1 + · · · + vd · q d−1
where q = (k + 1)p. Note that this sum cannot exceed q d , and so we have f (v) ∈ [N ]. An important
feature of our transformation is that there will be no carry bits that transfer between the “coordinates”
when summing k integers that correspond to vectors, and so f distributes over k-length sums of vectors in
V . In other words, for any set of k vectors v 1 , . . . , v k ∈ V , we have
!
!
k
k
k
X
X
X
vdi q d−1
v1i q 0 + · · · +
f (v i ) =
i=1

i=1

i=1

15

Note that

k
P

i=1

vji ≤

k
P

p ≤ kp, and so we have

i=1
k
X

v1i

i=1

And thus we have

k
P

i

f (v ) = f

i=1

!



0

q + ···+

k
X

vdi

i=1

k
P

i=1

!

q

d−1

=f

k
X

v

i=1

i

!


v , and so because V is a k-average-free set of vectors, it follows
i

that the corresponding integer set A = f (V ) is a k-average-free set of integers.

The final step in our proof is to verify that the set A has size Θ(N 1−ε ) when k = Ω(N δ ), as claimed.
δd
The parameters will work out correctly when we set k = ⌊p 1−δd ⌋ − 1. Note that we now have

d 
1
d
1−δd
= Θ(pd/(1−δd) )
N = ((k + 1)p) = Θ p
and so k = Ω(N δ ). Lastly, we must show that |A| = Ω(N 1−ε ). Recall that |A| ≥
a constant, which implies that |A| = Ω(pd−2 ). We must then show that

pd−2
d

and that d = ⌈3/ε⌉ is

pd−2 = Ω(N 1−ε ) = Ω((pd/(1−δd) )1−ε ) = Ω(p(1−ε)·d/(1−δd) )
Or, equivalently, that
d
1 − δd
(d − 2)(1 − δd) ≥ (1 − ε) · d
d − 2 ≥ (1 − ε) ·

d − 2 − δd2 + 2δd ≥ (1 − ε) · d
εd − 2 + (2δd − δd2 ) ≥ 0
Substituting in our previous choices of d ≥ 3/ε and δ =

1
2d2 ,

we can verify that this inequality holds:

εd − 2 + (2δd − δd2 ) ≥ 3 − 2 + (0 − 1/2) > 0.
This shows that |A| = Ω(N 1−ε ). To prove the claim that |A| = Θ(N 1−ε ), simply note that we may discard
elements from A at will without destroying its average freeness property.
From k-Average-Free sets to graphs. We are now ready to prove Lemma 1 which we repeat here for
convenience. The key idea is to let each node represent an integer in a careful way such that the k-average-free
property translatetes into the uniqueness of certain shortest paths.
Lemma 4. For all ε > 0, there is a 0 < δ < ε, and an infinite family of graphs G = (V, E) and pair sets
P ⊆ V × V with the following properties:
1. For each pair in P , there is a unique shortest path between its endpoints
2. These paths are edge disjoint
3. For all {s, t} ∈ P , we have distG (s, t) = ∆ for some value ∆ = Θ(nδ )
4. |P | = Θ(n2−ε )
Proof. Fix ε > 0 and apply Lemma 3 with parameter α = ε/2 > 0 to obtain an infinite sequence of integers N
and k-average-free sets A ⊆ [N ] of size |A| = Ω(N 1−α ), in which k = Ω(N β ) for some β > 0. We will assume
that 0 < β is no more than ε/10 (otherwise, we may decrease β without destroying the above properties).
Consider the infinite sequence of integers defined by n = N · k 2 = Θ(N 1+2β ), and we will describe how to
construct a graph G = (V, E) on n nodes that will be in our family, using the corresponding k-average-free
16

set A ⊆ [N ].
The Nodes. For each integer x ∈ [(k + 1) · N ] and “layer index” j ∈ {0, . . . , k}, we define a node (x, j)
and add it to G. In other words, we define
V := {(x, j) | x ∈ [(k + 1)N ], j ∈ {0, . . . , k}}.
The Edges. The edge set of G will be defined using the set A. Our graph will be layered such that all
edges have the form {(x, j), (y, j + 1)}. For all j ∈ {0, . . . , k − 1} and for each integer a ∈ A, we add an edge
{(x, j), (y, j + 1)} to E for all integers x, y ∈ [kN ] such that x + a = y. That is:
E := {{(x, j), (y, j + 1)} | j ∈ {0, . . . , k − 1}, ∃a ∈ A x + a = y}
The Pair Set. Next, we define our pair set P ⊆ V × V . For every integer x ∈ [N ] and integer a ∈ A,
we add the pair {s, t} to P where s = (x, 0) and t = (x + k · a, k). An immediate observation is that
|P | = N · |A| = Ω(N 2−α ). Formally:
P := {{(x, 0), (x + k · a, k)} | x ∈ [N ], a ∈ A}
We now turn to reasoning about the shortest paths between the pairs in P . First, note that for any pair
s = (x, 0) and t = (x + k · a, k) in P , the edge set
E s,t := {{(x + (j − 1) · a, j − 1), (x + j · a, j)} | j ∈ [k]}
forms a path of length k from s to t. We will refer to this path as ρ(s, t). Since our graph is layered, any
(s, t) path must contain at least k edges, and so ρ(s, t) is a shortest path between s and t. Additionally, any
other path ρ′ (s, t) of equal length must use an edge set of the form
E ′s,t = {{(yj−1 , j − 1), (yj−1 + aj , j)} | j ∈ [k], {yj } ∈ [kN ], {aj } ∈ A}.
Since these edges form a path from s to t, we deduce that y0 = x and yk = x + k · a. Combining this with
the equations for these k edges, we obtain
k−1
X
aj .
k·a=
j=0

Since A is a K-average free set, this implies that a = a0 = · · · = ak−1 , and so ρ′ (s, t) = ρ(s, t). Therefore,
ρ(s, t) is the unique shortest path between s and t, and its length is k =: ∆.
Next, we show that these shortest paths are edge disjoint. Any pair is determined by a starting point
(x, 0) for some x ∈ [N ] and an element a ∈ A. For any such pair, all the edges on the shortest path have the
form {(c, j), (c + a, j + 1)}. Therefore, two pairs that disagree on the element a cannot share any edge on
the shortest path. Moreover, if two pairs agree on the element a ∈ A but disagree on the starting point (i.e.
one starts at (x, 0) and the other starts at (y, 0)), then the corresponding shortest paths cannot even share
a node: all nodes on the first path have the form (x + j · a, j), while nodes on the second path have the form
(y + j · a, j). Therefore, the only way two paths can share a node is if a + j · a = b + j · a and so a = b.
To conclude the proof we bound the parameters of our construction. Since α = ε/2 and β < ε/10, we
have that


 2−α 
 2−ε/2 


9ε
|P | = Ω N 2−α = Ω n 1+2β ≥ Ω n 1+ε/5 = Ω n2− 2ε+10 ≥ Ω n2−ε

where last inequality follows from the fact that 0 < ε ≤ 1. In the statement of the lemma we actually
require that |P | = Θ(n2−ε ) as opposed to Ω(n2−ε ), but this follows because picking any appropriately-sized
subset of P , which will still satisfies all the other properties. Finally, note that the distances are k = Θ(N β )
β
which is Θ(nδ ) for δ = 1+2β
. Finally, this setting of δ straightforwardly implies that 0 < δ < β < ε, so the
condition 0 < δ < ε holds.

17

