arXiv:1703.10293v1 [] 30 Mar 2017

Preserving Distances in Very Faulty Graphs
Greg Bodwin

Fabrizio Grandoni

Stanford, gbodwin@stanford.edu

IDSIA, USI-SUPSI, fabrizio@idsia.ch

Merav Parter

Virginia Vassilevska Williams

CSAIL, MIT, parter@mit.edu

Stanford, virgi@cs.stanford.edu

Abstract
Preservers and additive spanners are sparse (hence cheap to store) subgraphs that preserve
the distances between given pairs of nodes exactly or with some small additive error, respectively. Since real-world networks are prone to failures, it makes sense to study fault-tolerant
versions of the above structures. This turns out to be a surprisingly difficult task. For every
small but arbitrary set of edge or vertex failures, the preservers and spanners need to contain
replacement paths around the faulted set. Unfortunately, the complexity of the interaction between replacement paths blows up significantly, even from 1 to 2 faults, and the structure of
optimal preservers and spanners is poorly understood. In particular, no nontrivial bounds for
preservers and additive spanners are known when the number of faults is bigger than 2.
Even the answer to the following innocent question is completely unknown: what is the
worst-case size of a preserver for a single pair of nodes in the presence of f edge faults? There
are no super-linear lower bounds, nor subquadratic upper bounds for f > 2. In this paper we
make substantial progress on this and other fundamental questions:
• We present the first truly sub-quadratic size single-pair preservers in unweighted (possibly
directed) graphs for any fixed number f of faults. Our result indeed generalizes to the
single-source case, and can be used to build new fault-tolerant additive spanners (for all
pairs).
• The size of the above single-pair preservers is O(n2−g(f ) ) for some positive function g,
and grows to O(n2 ) for increasing f . We show that this is necessary even in undirected
unweighted graphs, and even if you allow for a small additive error: If you aim at size
O(n2−ε ) for ε > 0, then the additive error has to be Ω(εf ). This surprisingly matches
known upper bounds in the literature.
• For weighted graphs, we provide matching upper and lower bounds for the single pair
case. Namely, the size of the preserver is Θ(n2 ) for f ≥ 2 in both directed and undirected
graphs, while for f = 1 the size is Θ(n) in undirected graphs. For directed graphs, we
have a superlinear upper bound and a matching lower bound.
Most of our lower bounds extend to the distance oracle setting, where rather than a subgraph
we ask for any compact data structure.

1

Introduction

Distance preservers and additive spanners are (sparse) subgraphs that preserve, either exactly or
with some small additive error, the distances between given critical pairs P of nodes. This has

been a subject of intense research in the last two decades [CE06, BW16, ADD+ 93, ACIM99, Che13,
BTMP05, AB16, Pet09].
However, real-world networks are prone to failures. For this reason, more recently (e.g. [CLPR09,
BCPS15,CP10,PP13,Par14,BGLP14,PP14,BGG+ 15,DK11,LNS02,CZ04,Luk99]) researchers have
devoted their attention to fault-tolerant versions of the above structures, where distances are (approximately) preserved also in the presence of a few edge (or vertex) faults. For the sake of simplicity
we focus here on edge faults, but many results generalize to the case of vertex faults where F ⊆ V .
Definition 1.1. Given an n-node graph G = (V, E) and P ⊆ V × V , a subgraph H ⊆ G is an
f -fault tolerant (f -FT) β-additive P -pairwise spanner if
distH\F (s, t) ≤ distG\F (s, t) + β,

∀(s, t) ∈ P, ∀F ⊆ E, |F | ≤ f.

If β = 0, then H is an f -FT P -pairwise preserver.
Finding sparse FT spanners/preservers turned out to be an incredibly challenging task. Despite
intensive research, many simple questions have remained open, the most striking of which arguably
is the following:
Question 1. What is the worst-case size of a preserver for a single pair (s, t) and f ≥ 1 faults?
Prior work [Par15, PP13] considered the single-source P = {s} × V unweighted case, providing
super-linear lower bounds for any f and tight upper bounds for f = 1, 2. However, first, there is
nothing known for f > 2, and second, the lower bounds for the {s} × V case do not apply to the
single pair case where much sparser preservers might exist. Prior to this work, it was conceivable
that in this case O(n) edges suffice for arbitrary fixed f .
Our first result is a complete answer to Question 1 for weighted graphs. In more detail, we
prove:
• An (s, t) preserver in a weighted graph for f = 1 has size Θ(n) in the undirected setting
(Theorem 4.1, with extensions in Theorem 4.3) or Θ(DP(n)) in the directed setting (Theorem
??).
• An (s, t) preserver in a weighted graph for f ≥ 2 has size Θ(n2 ) even in the undirected case
(Theorem 4.4).
The function DP(n) above denotes a tight bound for the sparsity of a pairwise distance preserver
in directed weighted graphs with n nodes and O(n) pairs. Coppersmith and Elkin [CE06] show
that Ω(n4/3 ) ≤ DP(n) ≤ O(n3/2 ). It is a major open question to close this gap, and we show
that the no-fault n-pair distance preserver question is equivalent to the 1-fault single pair preserver
question, thereby fully answering the latter question, up to resolving the major open problem for
n-pair preservers.
For unweighted graphs, we achieve several non-trivial lower bounds concerning the worst-case
size of (s, t) preservers and spanners:
• In the unweighted directed or undirected case this size is Θ(n) for f = 1. This shows an
interesting gap w.r.t. to the weighted case mentioned before.
• The size is super-linear for any f ≥ 2 even in unweighted undirected graphs and even if we
allow a small enough polynomial additive error nδ .
Note that the latter lower bound (unlike in the weighted case) leaves room for improvements.
In particular, consider the following question:
1

Question 2. In unweighted graphs, is the worst-case size of an f -FT (s, t) preserver subquadratic
for every constant f ≥ 2?
Prior work showed that the answer is YES for f = 1, 2 [Par15, PP14], but nothing is known for
f ≥ 3. We show that the answer is YES:
• In unweighted directed or undirected graphs, for any f ≥ 1 there is an (s, t) preserver of size
O(n2−g(f ) ) for some positive decreasing function g(·). See Theorem 2.1.
The above result has many strengths. First, it extends to the single-source case (i.e., P =
{s} × V ). Second, the same result holds for any fixed number f of vertex faults. Prior work was
only able to address the simple case f = 1 [Par14]. Third, such a preserver can be computed very
efficiently in O(f mn) time, and its analysis is relatively simple (e.g., compared to the slightly better
size bound in [Par15] that was achieved by a cumbersome case analysis). Finally, via fairly standard
techniques, the preserver result also implies improved f -FT 2-additive (all pairs!) spanners for all
f ≥ 1 (see Theorem 2.8).
In the above result the size of the preserver grows quickly to O(n2 ) for increasing f . This raises
the following new question:
Question 3. Does there exist a universal constant ε > 0 such that all unweighted graphs have an
f -FT (s, t) preserver of size Of (n2−ε )? What if we allow a small additive error?
The only result with strongly sub-quadratic size in the above sense is an O(f · n4/3 ) size spanner
with additive error Θ(f ) [BCPS15,BGG+ 15]. Can we remove or reduce the dependence of the error
on f ? We show that the answer is NO:
• In undirected unweighted graphs, any single-pair spanner of strongly subquadratic size Of (n2−ε )
for ε > 0 needs to have additive error Ω(εf ). (See Theorem 3.1 and related results in Theorems 3.4-3.5).
Hence the linear dependence in f in the additive error in [BCPS15, BGG+ 15] is indeed necessary.
We found this very surprising. The table in Appendix A summarizes our main results for FTpreservers.
So far we have focused on sparse distance preserving subgraphs. However, suppose that the
distance estimates can be stored in a different way in memory. Data structures that store the
distance information of a graph in the presence of faults are called distance sensitivity oracles.
Distance sensitivity oracles are also intensely studied [DTCR08,BK09,WY13, GW12, DP09, DP17].
Our main goal here is to keep the size of the data structure as small as possible. Other typical
goals are to minimize preprocessing and query time - we will not address these.
Question 4. How much space do we need to preserve (exactly or with a small additive error) the
distances between a given pair of nodes in the presence of f faults?
Clearly all our preserver/spanner upper bounds extend to the oracle case, however the lower
bounds might not: in principle a distance oracle can use much less space than a preserver/spanner
with the same accuracy. Our main contribution here is the following incompressibility result:
• The worst-case size of a single-pair exact distance sensitivity oracle in directed or undirected
weighted graphs is Θ(n2 ) for f ≥ 2 (note that the optimal size for f = 1 is Θ(n) by simple
folklore arguments, so our result completes these settings). See Theorem 4.4.

2

• If we allow for a polynomial additive error nδ , for small δ, even in the setting of undirected
unweighted graphs, then the size of the oracle has to be super-linear already for f ≥ 3
(Theorem 3.6).
The technical part of the paper has precise theorem statements for all results. The interested
reader will find even more results and corollaries there as well. We omitted these from this introduction for the sake of clarity.

1.1

Related Work

Fault-tolerant spanners were introduced in the geometric setting [LNS02] (see also [Luk99, CZ04]).
FT-spanners with multiplicative stretch are relatively well understood: the error/sparsity for f -FT
and f -VFT multiplicative spanners is (up to a small polynomial factor in f ) the same as in the
nonfaulty case. For f edge faults, Chechik et al. [CLPR09] showed how to construct f -FT (2k − 1)1
multiplicative spanners with size Õ(f n1+ k ) for any f, k ≥ 1. They also construct an f -VFT spanner
with the same stretch and larger size. This was later improved by Dinitz and
[DK11]
 Krauthgamer

2− k1 1+ k1
who showed the construction of f -VFT spanners with 2k − 1 error and Õ f
n
edges.
FT additive spanners were first considered by Braunschvig, Chechik and Peleg in [BCPS15] (see
also [BGG+ 15] for slightly improved results). They showed that FT Θ(f )-additive spanners can
be constructed by combining FT multiplicative spanners with (non-faulty) additive spanners. This
construction, however, supports only edge faults. Parter and Peleg showed in [PP14] a lower bound
of Ω(n1+εβ ) edges for single-source FT β-additive spanners. They also provided a construction of
single-source FT-spanner with additive stretch 4 and O(n4/3 ) edges that is resilient to one edge
fault. The first constructions of FT-additive spanners resilient against one vertex fault were given
in [Par14] and later on in [BGG+ 15]. Prior to our work, no construction of FT-additive spanners
was known for f ≥ 2 vertex faults.
As mentioned earlier, the computation of preservers and spanners in the non-faulty case (i.e.
when f = 0) has been the subject of intense research in the last few decades. The current-best
preservers can be found in [CE06, BW16, Bod17b]. Spanners are also well understood, both for
multiplicative stretch [ADD+ 93,Erd63] and for additive stretch [ACIM99,Che13,BTMP05,Woo10,
AB16, BW16, Che13, Pet09, ABP17]. There are also a few results on “mixed” spanners with both
multiplicative and additive stretch [EP04, TZ06, BTMP05]
Distance sensitivity oracles are data structures that can answer queries about the distances in
a given graph in the presence of faults. The first nontrivial construction was given by Demetrescu
et al. [DTCR08] and later improved by Bernstein and Karger [BK09] who showed how to construct
Õ(n2 )-space, constant query time oracles for a single edge fault for an m-edge n-node graph in
Õ(mn) time. The first work that considered the case of two faults (hence making the first jump
from one to two) is due to Duan and Pettie in [DP09]. Their distance oracle has nearly optimal
e 2 ) and query time of O(1).
e
size of O(n
The case of bounded edge weights, and possibly multiple
faults, is addressed in [WY13, GW12] exploiting fast matrix multiplication techniques. The size of
their oracle is super-quadratic.
The notion of FT-preservers is also closely related to the problem of constructing replacement
paths. For a pair of vertices s and t and an edge e, the replacement path Ps,t,e is the s-t shortestpath that avoids e1 . The efficient computation of replacement paths is addressed, among others,
in [MMG89, RZ12, WY13, VW11]. A single-source version of the problem is studied in [GW12].
Single-source FT structures that preserve strong connectivity have been studied in [BCR16].
1

Replacement paths were originally defined for the single edge fault case, but later on extended to the case of
multiple faults as well.

3

1.2

Preliminaries and Notation

Assume throughout that all shortest paths ties are broken in a consistent manner. For every s, t ∈ V
and a subgraph G0 ⊆ G, let πG0 (s, t) be the (unique) u-v shortest path in G0 (i.e., it is unique under
breaking ties). If there is no path between s and t in G0 , we define πG0 (s, t) = ∅. When G0 = G,
we simply write π(u, v). For any path P containing nodes u, v, let P [u
v] be the subpath of P
between u and v. For s, t ∈ V and F ⊆ E, we let Ps,t,F = πG\F (s, t) be the s-t shortest-path in
G \ F . We call such paths replacement paths. When F = {e}, we simply write Ps,t,e . By m we
denote the number of edges in the graph currently being considered.
The structure of the paper is as follows. In Sec. 2, we describe an efficient construction for
FT-preservers and additive spanners with a subquadratic number of edges. Then, in Sec. 3, we
provide several lower bound constructions for a single s-t pair, both for the exact and for the
additive stretch case. Finally, in Sec. 4 we consider the setting of weighted graphs. Most of the
results of that setting are deferred to Appendix ??. Missing proofs in other sections can be found
in the appendix as well.

2

Efficient Construction of FT-Preservers and Spanners

In this section we show:
Theorem 2.1. For every directed or undirected unweighted graph G = (V, E), integer f ≥ 1 and
S ⊆ V , one can construct in time O(f n m) an f -FT S-sourcewise (i.e. P = S × V ) preserver of
e · |S|1/2f · n2−1/2f ).
size O(f
We remark that Theorem 2.1 holds under both edge and vertex faults. We next focus on
the directed case, the undirected one being analogous and simpler. We begin by recapping the
currently-known approaches for handling many faults, and we explain why these approaches fail to
achieve interesting space/construction time bounds for large f .
The limits of previous approaches: A known approach for handling many faults is by random
sampling of subgraphs, as introduced by Weimann and Yuster [WY13] in the setting of distance
sensitivity oracles, and later on applied by Dinitz and Kraughgamer [DK11] in the setting of fault
tolerant spanners. The high level idea is to generate multiple subgraphs G1 , . . . , Gr by removing
each edge/vertex independently with sufficiently large probability p; intuitively, each Gi simultaneously captures many possible fault sets of size f . One can show that, for a sufficiently small
parameter L and for any given (short) replacement path Ps,t,F of length at most L (avoiding faults
F ), w.h.p. in at least one Gi the path Ps,t,F is still present while all edges/vertices in F are
S deleted.
Thus, if we compute a (non-faulty) preserver Hi ⊆ Gi for each i, then the graph H = i Hi will
contain every short replacement path. For the remaining (long) replacement paths, Weimann and
Yuster use a random decomposition into short subpaths. Unfortunately, any combination of the
parameters p, r, L leads to a quadratic (or larger) space usage.
Another way to handle multiple faults is by extending the approach in [PP13,PP14,Par14] that
works for f ∈ {1, 2}. A useful trick used in those papers (inspired by prior work in [RZ12, VW11])
is as follows: suppose f = 1, and fix a target node t. Consider the shortest path π(s, t). It is
sufficient to take the last edge of each replacement path Ps,t,e and charge it to the node t; the rest
of the path is then charged to other nodes by an inductive argument. Hence, one only needs to
bound the number of new-ending paths – those that end in an edge that is not already in π(s, t).
In the case f = 1, these new-ending paths have a nice structure: they diverge from π(s, t) at
some vertex b (divergence point) above the failing edge/vertex and collide again with π(s, t) only
4

at the terminal t; the subpath connecting b and t on the replacement path is called its detour. One
can divide the s-t replacement paths into two groups: short (resp., long) paths are those whose
√
detour has length at most (resp., at least) n. It is then straightforward enough to show that each
e 1/2 ) edges entering t, and so (collecting these last edges over
category of path contributes only O(n
e 3/2 ) edges in total. Generalizing this to the
all nodes in the graph) the output subgraph has O(n
case of multiple faults is non-trivial already for the case of f = 2. The main obstacle here stems
from a lack of structural understanding of replacement paths for multiple faults: in particular, any
given divergence point b ∈ π(s, t) can now be associated with many new-ending paths and not only
one! In the only known positive solution for f = 2 [Par15], the approach works only for edge faults
and is based on an extensive case analysis whose extension to larger f is beyond reasonable reach.
Thus, in the absence of new structural understanding, further progress seems very difficult.
A second source of difficulties is related to the running time of the construction. A priori, it
seems that constructing a preserver H should require computing all replacement paths Ps,t,F , which
leads to a construction time that scales exponentially in f . In particular, by deciding to omit an
edge e from the preserver H, we must somehow check that this edge does not appear on any of the
replacement paths Ps,t,F (possibly, without computing these replacement paths explicitly).
Our basic approach: The basic idea behind our algorithm is as follows. Similar to [PP13, PP14,
Par14], we focus on each target node t, and define a set Et of edges incident to t to be added to
our preserver. Intuitively, these are the last edges of new-ending paths as described before. The
construction of Et , however, deviates substantially from prior work. Let us focus on the simpler
case of edge deletions. The set Et is constructed recursively, according to parameter f . Initially we
consider the shortest path tree T from the source set S to t, and add to Et the edges of T incident
to t (at most |S| many). Consider any new-ending replacement path P for t. By the previous
discussion, this path has to leave T at some node b and it meets T again only at t: let D be the
subpath of P between b and t (the detour of P ). Note that D is edge-disjoint from T , i.e. it is
contained in the graph G0 = G \ E(T ). Therefore, it would be sufficient to compute recursively the
set Et0 of final edges of new-ending replacement paths for t in the graph G0 with source set S 0 given
by the possible divergence points b and w.r.t. f − 1 faults (recall that one fault must be in E(T ),
hence we avoid that anyway in G0 ). This set Et0 can then be added to Et .
The problem with this approach is that S 0 can contain Ω(n) many divergence points (hence Et
Ω(n) many edges), leading to a trivial Ω(n2 ) size preserver. In order to circumvent this problem,
we classify the divergence points b in two categories. Consider first the nodes b at distance at
most L from t along T , for some parameter L. There are only O(|S|L) many such nodes S short ,
which is sublinear for |S| and L small enough. Therefore we can safely add S short to S 0 . For the
remaining divergence points b, we observe that the corresponding detour D must have length at
least L: therefore by sampling Õ(n/L) nodes S long we hit all such detours w.h.p. Suppose that
σ ∈ S long hits detour D. Then the portion of D from σ to t also contains the final edge of D to be
added to Et . In other terms, it is sufficient to add S long (which has sublinear size for polynomially
large L) to S 0 to cover all the detours of nodes b of the second type. Altogether, in the recursive
call we need to handle one less fault w.r.t. a larger (but sublinear) set of sources S 0 . Our approach
has several benefits:
• It leads to a subquadratic size for any f (for a proper choice of the parameters);
• It leads to a very fast algorithm. In fact, for each target t we only need to compute a BFS
tree in f different graphs, leading to an O(f nm) running time;
• Our analysis is very simple, much simpler than in [Par15] for the case f = 2;
• It can be easily extended to the case of vertex faults.
5

Algorithm 1 Construction of Et in our f -FT S-Sourcewise Preserver Algorithm.
1:

2:
3:
4:
5:
6:
7:
8:
9:

procedure ComputeSourcewiseFT(t, S, f, G)
Input: A graph G with a source set S and terminal t, number of faults f .
Output: Edges Et incident to t in an f -FT S-sourcewise preserver H.
Set G0 = G, S0 = S, Et = ∅.
for i ∈ {0, . . . , f } do
S
Compute the partial BFS tree Ti = s∈Si πGi (s, t).
Et = Et ∪ {LastE(πTi (s, t)) p
| s ∈ Si }.
Set distance threshold di = n/|Si | · f log n.
Let Sishort = {v ∈ V (Ti ) | distTi (v, t) ≤ di }.
Sample a collection Silong ⊆ V (Gi ) of Θ(n/di · f log n) vertices.
Set Si+1 = Sishort ∪ Silong and Gi+1 = Gi \ E(Ti ).

Algorithm for Edge Faults: Let us start with the edge faults case. The algorithm constructs
a set SEt of edges incident to each target node t ∈ V . The final preserver is simply the union
H = t∈V Et of these edges. We next describe the construction of each Et (see also Alg. 1). The
computation proceeds in rounds i = 0, . . . , f . At the beginning of round i we are given a subgraph
Gi (with G0 = G) and a set of sources Si (with
S S0 = S).
We compute a partial BFS tree Ti = s∈Si πGi (s, t)2 from Si to t, and add to Et (which is
initially empty) the edges {LastE(πTi (s, t)) | s ∈ Si } of this tree incident to t. Here, for a path π
where one endpoint is the considered target node t, we denote by LastE(π) the edge of π incident
to t. The source set Si+1 is given by Sishort ∪ Silong . Here Sishort = {v ∈ V (Ti ) | distTi (v, t) ≤ di }
p
is the set of nodes at distance at most di = n/|Si | · f log n from t, while Silong is a random sample
of Θ(n/di · f log n) vertices. The graph Gi+1 is obtained from Gi be removing the edges E(Ti )3 .
Adaptation for Vertex Faults: The only change in the algorithm is in the definition of the graph
Gi inside the procedure to compute Et . We cannot allow ourselves to remove all the vertices of the
tree Ti from Gi and hence a more subtle definition is required. To define Gi+1 , we first remove from
Gi : (1) all edges of Sishort × Sishort , (2) the edges of E(Ti ), and (3) the vertices of V (Ti ) \ Sishort . In
addition, we orient all remaining edges incident to Sishort to be directed away from these vertices
(i.e., the incoming degree of the Sishort vertices in Gi+1 is zero). Finally, we delete all remaining
edges incident to Sishort which are directed towards any one of these vertices (i.e., the incoming
degree of the Sishort vertices in Gi+1 is zero).
Analysis: We now analyze our algorithm. Since for each vertex t, we compute f (partial) BFS
trees, we get trivially:
Lemma 2.2 (Running Time). The subgraph H is computed within O(f n m) time.
We proceed with bounding the size of H.
1/2f · (f n)1−1/2f ) for every t ∈ V , hence |E(H)| =
e
Lemma 2.3 (Size Analysis). |Et | = O(|S|
f
f
e |S|1/2 n2−1/2 ).
O(f
Proof. Since the number of edges collected at the end each round i is bounded by the number of
sources Si , it is sufficient to bound |Si | for all i. Observe that, for every i ∈ {0, . . . , f − 1},
|Si+1 | ≤ |Silong | + |Sishort | ≤ di · |Si | + Θ(n/di · f log n) = Θ(di · |Si |).
2

If πGi (s, t) does not exist, recall that we define it as an empty set of edges.
Note that for f = 1, the algorithm has some similarity to the replacement path computation of [RZ12]. Yet,
there was no prior extension of this idea for f ≥ 2.
3

6

i

i

By resolving this recurrence starting with |S0 | = |S| one obtains |Si | = O(|S|1/2 (f n log n)1−1/2 ).
The claim follows by summing over i ∈ {0, . . . , f }.
We next show that the algorithm is correct. We focus on the vertex fault case, the edge fault
case being similar and simpler. Let us define, for t ∈ V and i ∈ {0, . . . , f },
Pt,i = {πGi \F (s, t) | s ∈ Si , F ⊆ V (Gi ), |F | ≤ f − i}.
Lemma 2.4. For every t ∈ V and i ∈ {0, . . . , f }, it holds that: LastE(π) ∈ Et for every

π ∈ Pt,i .

Proof. We prove the claim by decreasing induction on i ∈ {f, . . . , 0}. For the base of the induction,
consider the case of i = f . In this case, Pt,f = {πGf (s, t) | s ∈ Sf }. Since we add precisely
the last edges of these paths to the set Et , the claim holds. Assume that the lemma holds for
0
rounds f, f − 1, . . . , i + 1 and consider round i. For every πGi \F (s, t) ∈ Pt,i , let Ps,t,F
= πGi \F (s, t).
S
4 Consider the partial BFS tree T =
i
s∈Si πGi (s, t) rooted at t. Note that all (interesting)
0
0
replacement paths Ps,t,F
in Gi have at least one failing vertex v ∈ F ∩ V (Ti ) as otherwise Ps,t,F
=
πGi (s, t).
We next partition the replacement paths π ∈ Pt,i into two types depending on their last edge
LastE(π). The first class contains all paths whose last edge is in Ti . The second class of replacement
paths contains the remaining paths, which end with an edge that is not in Ti . We call this second
class of paths new-ending replacement paths. Observe that the first class is taken care of, since we
add all edges incident to t in Ti . Hence it remains to prove the lemma for the set of new-ending
paths.
0
0
For every new-ending path Ps,t,F
, let bs,t,F be the last vertex on Ps,t,F
that is in V (Ti ) \ {t}.
We call the vertex bs,t,F the last divergence point of the new-ending replacement path. Note that
0
[bs,t,F
t] is vertex disjoint with the tree Ti except for the vertices bs,t,F
the detour Ds,t,F = Ps,t,F
and t. From now on, since we only wish to collect last edges, we may restrict our attention to
0
this detour subpath. That is, since LastE(Ds,t,F ) = LastE(Ps,t,F
), it is sufficient to show that
LastE(Ds,t,F ) ∈ Et .
Our approach is based on dividing the set of new-ending paths in Pt,i into two classes based
on the position of their last divergence point bs,t,F (see Fig. 1). The first class Pp
short consists of
new-ending paths in Pt,i whose last divergence point is at distance at most di = n/|Si | · f log n
from t on Ti . In other words, this class contains all new-ending paths whose last divergence point
is in the set Sishort . We now claim the following.
0
Claim 2.5. For every Ps,t,F
∈ Pshort , the detour Ds,t,F is in Pt,i+1 .
0
Proof. Since Ds,t,F is a subpath of the replacement path Ps,t,F
, Ds,t,f is the shortest path between
bs,t,F and t in Gi \ F . Recall that Ds,t,F is vertex disjoint with V (Ti ) \ {bs,t,F , t}.
0
Since bs,t,F is the last divergence point of Ps,t,F
with Ti , the detour Ds,t,F starts from a vertex
short
bs,t,F ∈ Si
and does not pass through any other vertex in V (Ti ) \ {t}. Since we only changed in
Gi+1 the direction of edges incident to Sishort vertices but the outgoing edge connecting bs,t,F to its
neighbor x on Ds,t,F [bs,t,F
t] remains (i.e., this vertex x is not in V (Ti ) \ {t}), this implies that
the detour Ds,t,F exists in Gi+1 . In particular, note that the vertex bs,t,F cannot be a neighbor of t
in Ti . If (bs,t,F , t) were an edge in Ti , then we can replace the portion of the detour path between
0
bs,t,F and t by this edge, getting a contradiction to the fact that Ps,t,F
is a new-ending path5 .
0
We denote these replacement paths as Ps,t,F
as they are computed in Gi and not in G.
For the edge fault case, the argument is much simpler: by removing E(Ti ) from Gi , we avoid at least one the
failing edges in Gi+1 .
4
5

7

𝑠1𝑖

𝑠2𝑖

𝑠𝜎𝑖

𝑠𝑗𝑖

𝑠3𝑖

𝑃𝑠𝜎 ,𝑡,𝐹′
𝑏𝑠𝜎 ,𝑡,𝐹′
𝑤𝑠𝜎 ,𝑡,𝐹′

𝑃𝑠1 ,𝑡,𝐹

𝑠ℓ𝑖

𝑏𝑠1 ,𝑡,𝐹
𝐷𝑠1 ,𝑡,𝐹

𝑡

Figure 1: Shown is a partial tree Ti whose leaves set are in Si , all edges are directed towards t in the directed
case. (In the figure, we let sij = si for simplicity of notation). The replacement paths Psij ,t,F are divided
into two types depending on their last divergence point bsij ,t,F . Note that this point is not necessarily on
π(sij , t) and may appear on other π(si` ) paths. The vertices appearing on the first di levels of Ti are Sishort .
The path Ps1 ,t,F is in Pshort and the path Psσ ,t,F 0 is in Plong . The vertex wsσ ,t,F 0 is in the set Silong and it
hits the long detour of Psσ ,t,F 0 . Note that since both Ps1 ,t,F and Psσ ,t,F are new-ending, one of the vertices
in their failing set F, F 0 appears on πTi (bs1 ,t,F , t), πTi (bsσ ,t,F 0 , t) respectively.

Next, observe that at least one of the failing vertices in F occurs on the subpath πGi [bs,t,F , t],
let this vertex be v ∈ F . Since v ∈ Sishort , all the edges are directed away from v in Gi+1 and hence
the paths going out from the source bs,t,F in Gi+1 cannot pass through v. Letting F 0 = F \ V (Ti ),
it holds that (1) |F 0 | ≤ f − i − 1 and (2) since the shortest path ties are decided in a consistent
manner and by definition of Gi+1 , it holds that Ds,t,F = πGi+1 \F 0 (bs,t,F , t). As bs,t,F ∈ Sishort , it
holds that Ds,t,F ∈ Pt,i+1 .
0
0
Hence by the inductive hypothesis for i + 1, LastE(Ps,t,F
) is in Et for every Ps,t,F
∈ Pshort .
We now turn to consider the second class of paths Plong which contains all remaining new-ending
paths; i.e., those paths whose last divergence point is at distance at least di from t on Ti . Note
0
[bs,t,F
t] of these paths is long – i.e., its length is at least di . For
that the detour Ds,t,F = Ps,t,F
0
convenience, we will consider the internal part Ds,t,F
= Ds,t,F \ {bs,t,F , t} of these detours, so that
the first and last vertices of these detours are not on Ti .
0
We exploit the lengths of these detours Ds,t,F
and claim that w.h.p, the set Silong is a hitting
set for these detours. This indeed holds by simple union bound overall possible O(nf +2 ) detours.
0
0
For every Ps,t,F
∈ Plong , let ws,t,F ∈ V (Ds,t,F
) ∩ Silong . (By the hitting set property, w.h.p., ws,t,F
0
0
is well defined for each long detour). Let Ws,t,F = Ps,t,F
[ws,t,F , t] be the suffix of the path Ps,t,F
0
starting at a vertex from the hitting set ws,t,F ∈ Silong . Since LastE(Ps,t,F
) = LastE(Ws,t,F ), it is
sufficient to show that LastE(Ws,t,F ) is in Et .
0
Claim 2.6. For every Ps,t,F
∈ Plong , it holds that Ws,t,F ∈ Pt,i+1 .
0
Proof. Clearly, Ws,t,f is the shortest path between ws,t,F and t in Gi \ F . Since Ws,t,F ⊆ Ds,t,F
is
0
vertex disjoint with V (Ti ), it holds that Ws,t,F = πGi+1 \F 0 (ws,t,F , t) for F = F \ V (Ti ). Note that
since at least one fault occurred on Ti , we have that |F 0 | ≤ f − i − 1. As ws,t,F ∈ Silong , it holds
that Ws,t,F ∈ Pt,i+1 . The lemma follows.
0
By applying the claim for i = 0, we get that LastE(Ps,t,F
) is in Et as required for every
∈ Plong . This completes the proof.

0
Ps,t,F

Lemma 2.7. (Correctness) H is an f -FT S-sourcewise preserver.

8

Proof. By using Lemma 2.4 with i = 0, we get that for every t ∈ V , s ∈ S and F ⊆ V , |F | ≤ f ,
LastE(Ps,t,F ) ∈ Et (and hence also LastE(Ps,t,F ) ∈ H). It remains to show that taking the last
edge of each replacement path Ps,t,F is sufficient. The base case is for paths of length 1, where we
have clearly kept the entire path in our preserver. Then, assuming the hypothesis holds for paths
up to length k − 1, consider a path Ps,t,F of length k. Let LastE(Ps,t,F ) = (u, t). Then since we
break ties in a consistent manner, Ps,t,F = Ps,u,F ◦ LastE(Ps,t,e ). By the inductive hypothesis Ps,u,F
is in H, and since we included the last edge, Ps,t,F is also in H. The claim follows.
Theorem 2.1 now immediately follows from Lemmas 2.2, 2.3, and 2.7. Combing our f -FT
sourcewise preserver from Theorem 2.1 with standard techniques (see, e.g. [Par14]), we show:
Theorem 2.8. For every undirected unweighted graph G = (V, E) and integer f ≥ 1, there exists a
e nm)-time construction of a +2-additive f -FT spanner of G of size O(f
e ·n2−1/(2f +1) )
randomized O(f
that succeeds w.h.p.6 .
Proof. The spanner construction works as follows. Let L be an integer parameter to be fixed later.
A vertex u is low-degree if it has degree less than L, otherwise it is high-degree. Let S be a random
sample of Θ( Ln · f log n) vertices. Our spanner H consists of the f -VFT S-sourcewise preserver from
Theorem 2.1 plus all the edges incident to low-degree vertices. We now analyze the construction.
The size of H is bounded by:




e f |S|1/2f · n2−1/2f + O(nL) = O
e f 1+1/2f L−1/2f · n2 + nL
O
l
m
f
f
The claim on the size follows by choosing L = f n2 /(2 +1) .
Next, we turn to show correctness. First note that w.h.p every high-degree vertex has at least
f + 1 neighbors in S. Consider any pair of vertices u, t and a set of failing vertices F and let Pu,t,F
be the u − t shortest path in G \ F . Let x be the last vertex (closest to t) incident to a missing
edge e ∈ Pu,t,F \ E(H). Hence x is a high-degree vertex. We observe that, w.h.p., x is adjacent
to at least f + 1 vertices in S. Since at most f vertices fail, one of the neighbors of x in S ,say,
s0 survives. Let πH\F (u, s0 ) be the u − s0 shortest path in H \ F , and consider the following u − t
path P 0 = πH\F (u, s0 ) · (s0 , x) · Pu,t,F [x
t]. By the definition of x, P 0 ⊆ H. In addition, since H
contains an f -FT S-sourcewise preserver and s0 ∈ S, it holds that
distH\F (u, t) ≤ |P 0 | = distG\F (u, s0 ) + 1 + |Pu,t,F [x
≤ distG\F (u, x) + 2 + Pu,t,f [x

t]|

t] = |Pu,t,F | + 2 = distG\F (u, t) + 2.

The lemma follows.

3

Lower Bounds for FT Preservers and Additive Spanners

In this section, we provide the first non-trivial lower bounds for preservers and additive spanners
for a single pair s-t. We start by proving the following theorem.
Theorem 3.1. For any two integers q, h > 0 and a sufficiently large n, there exists an unweighted
undirected n-node graph G = (V, E) and a pair s, t ∈ V such that any 2hq-FT (2q − 1)-additive
n 2−2/(h+1)
)
).
spanner for G for the single pair (s, t) has size Ω(( hq
6

The term w.h.p. (with high probability) here indicates a probability exceeding 1 − 1/nc , for an arbitrary constant
c ≥ 2. Since randomization is only used to select hitting sets, the algorithm can be derandomized; details will be
given in the journal version.

9

The main building block in our lower bound is the construction of an (undirected unweighted)
tree T h , where h is a positive integer parameter related to the desired number of faults f . Tree T h
is taken from [Par15] with mild technical adaptations. Let d be a size parameter which is used to
obtain the desired number n of nodes. It is convenient to interpret this tree as rooted at a specific
node (though edges in this construction are undirected). We next let rt(T h ) and L(T h ) be the root
and leaf set of T h , respectively. We also let `(h) and n(h) be the height and number of nodes of
T h , respectively.
Tree T h is constructed recursively as follows (see also Fig. 3a). The base case is given by T 0
which consists of a single isolated root node rt(T 0 ). Note that `(0) = 0 and n(0) = 1. In order to
h−1
construct T h , we first create d copies T0h−1 , . . . , Td−1
of T h−1 . Then we add a path v0 , . . . , vd−1 of
length d − 1 (consisting of new nodes), and choose rt(T h ) = v0 . Finally, we connect vj to rt(Tjh−1 )
with a path (whose internal nodes are new) of length (d − j) · (`(h − 1) + 3). Next lemma illustrates
the crucial properties of T h .
Lemma 3.2. The tree T h satisfies the following properties:
1. n(h) ≤ 23 (h + 1)(d + 1)h+1
2. |L(T h )| = dh
3. For every ` ∈ L(T h ), there exists F` ⊆ E(T ), |F` | = h, such that distT h \F` (s, `) ≤
distT h \F` (s, `0 ) + 2 for every `0 ∈ L(T h ) \ {`0 }.
We next construct a graph S h as follows. We create two copies Ts and Tt of T h . We add to
S h the complete bipartite graph with sides L(Ts ) and L(Tt ), which we will call the bipartite core
B of S h . Observe that |L(Ts )| = |L(Tt )| = dh , and hence B contains d2h edges. We will call
s = sr(S h ) = rt(Ts ) the source of S h , and t = tg(S h ) = rt(Tt ) its target. See Fig. 3b for an
illustration.
Lemma 3.3. Every 2h-FT (s, t) preserver (and 1-additive (s, t) spanner) H for S h must contain
each edge e = (`s , `t ) ∈ B.
Proof. Assume that e = (`s , `t ) ∈
/ H and consider the case where F`s fails in Ts and F`t fails in Tt .
Let G0 := S h \ (F`s ∪ F`t ), and ds (resp., dt ) be the distance from s to `s (resp., from `t to t) in G0 .
By Lemma 3.2.3 the shortest s-t path in G0 passes through e and has length ds + 1 + dt . By the
same lemma, any path in G0 , hence in H 0 := H \ (F`s ∪ F`t ), that does not pass through `s (resp.,
`t ) must have length at least (ds + 2) + 1 + dt (resp., ds + 1 + (dt + 2)). On the other hand, any
path in H 0 that passes through `s and `t must use at least 3 edges of B, hence having length at
least ds + 3 + dt .
Our lower bound graph Sqh (see also Fig. 3d) is obtained by taking q copies S1 , . . . , Sq of graph
1

n
S h with d = ( 3q(h+1)
− 1) h+1 , and chaining them with edges (tg(Si ), sr(Si+1 )), for i = 1, . . . , q − 1.
We let s = sr(S1 ) and t = tg(Sq ).

Proof of Theorem 3.1. Consider Sqh . By Lemma 3.2.1-2 this graph contains at most n nodes, and
n 2−2/(h+1)
the bipartite core of each Si contains d2h = Ω(( qh
)
) edges.
Finally, we show that any (2q − 1)-additive (s, t) spanner needs to contain all the edges of at
least one such bipartite core. Let us assume this does not happen, and let ei be a missing edge
in the bipartite core of Si for each i. Observe that each s-t shortest path has to cross sr(Si ) and
tg(Si ) for all i. Therefore, it is sufficient to choose 2h faulty edges corresponding to each ei as in
Lemma 3.3. This introduces an additive stretch of 2 in the distance between s and t for each ei ,
leading to a total additive stretch of at least 2q.
10

The same construction can also be extended to the setting of (2h)-FT S × T preservers. To do
that, we make parallel copies of the S h graph. Details are given in Appendix B.4.
Improving over the Bipartite Core: The proof above only gives the trivial lower bound of
Ω(n) for the case of two faults (using h = q = 1). We can strengthen the proof in this special case
to show instead that Ω(n1+ε ) edges are needed, and indeed this even holds in the presence of a
polynomial additive stretch:
Theorem 3.4. A 2-FT distance preserver of a single (s, t) pair in an undirected unweighted graph
needs Ω(n11/10−o(1) ) edges.
Theorem 3.5. There are absolute constants ε, δ > 0 such that any +nδ -additive 2-FT preserver
for a single (s, t) pair in an undirected unweighted graph needs Ω(n1+ε ) edges.
Finally, by tolerating one additional fault, we can obtain a strong incompressibility result:
Theorem 3.6. There are absolute constants ε, δ > 0 such that any +nδ -additive 3-FT distance
sensitivity oracle for a single (s, t) pair in an undirected unweighted graph uses Ω(n1+ε ) bits of
space.
The proofs of Theorems 3.4, 3.5 and 3.6 are all given in Appendix B. The central technique in
their proofs, however, is the same. The key observation is that the structure of Ts , Tt allows us to
use our faults to select leaves `s , `t and enforce that a shortest `s − `t path is kept in the graph.
When we use a bipartite core between the leaves of Ts and Tt , this “shortest path” is simply an
edge, so the quality of our lower bound is equal to the product of the leaves in Ts and Tt . However,
sometimes a better graph can be used instead. In the case h = 1, we can use a nontrivial lower
bound graph against (non-faulty) subset distance preservers (from [Bod17a]), which improves the
cost per leaf pair from 1 edge to roughly n11/10 edges, yielding Theorem 3.4. Alternatively, we can
use a nontrivial lower bound graph against +nδ spanners (from [AB16]), which implies Theorem 3.5.
The proof of Theorem 3.6 is similar in spirit, but requires an additional trick in which unbalanced
trees are used: we take Ts as a copy of T 1 and Tt as a copy of T 2 , and this improved number of
leaf-pairs is enough to push the incompressibility argument through.

4

FT Pairwise Preservers for Weighted Graphs

We now turn to consider weighted graphs, for which the space requirements for FT (s, t) preservers
are considerably larger.
Theorem 4.1. For any undirected weighted graph G and pair of nodes (s, t), there is a 1-FT (s, t)
preserver with O(n) edges.
To prove Thm. 4.1, we first need:
Lemma 4.2. In an undirected weighted graph G, for any replacement path Ps,t,e protecting against
a single edge fault, there is an edge (x, y) ∈ Ps,t,e such that there is no shortest path from s to x in
G that includes e, and there is no shortest path from t to y in G that includes e.
Proof. Let x be the furthest node from s in Ps,t,e such that there is no shortest path from s to x in
G that includes e. Note that if x = t then there is no path from s to t that uses e and so the claim
holds trivially. We can therefore assume x 6= t, and define: let y be the node immediately following
x in Ps,t,e . It must then be the case that there is a shortest path from s to y that includes e.
11

Let e =: (u, v), with dist(s, u) < dist(s, v). The shortest path from s to y that uses e must then
intersect u before v, so we have dist(u, y) > dist(v, y). Thus, any shortest path in G beginning at
y that uses (u, v) must intersect v before u. However, we have dist(u, t) > dist(v, t). Therefore,
any shortest path ending at t that uses (u, v) must intersect u before v. It follows that any shortest
path beginning at y and ending at t does not use (u, v).
We can now prove:
Proof of Theorem 4.1. To construct the preserver, simply add shortest path trees rooted at s and
t to the preserver. If the edge fault e does not lie on the included shortest path from s to t, then
the structure is trivially a preserver. Thus, we may assume that e is in π(s, t). We now claim
that, for some valid replacement path Ps,t,e protecting against the fault e, all but one (or all) of
the edges of Ps,t,e are in the preserver. To see this, we invoke Lemma 4.2: there is an edge (x, y)
in Ps,t,e such that no shortest path from s to x and no shortest path from t to y in G Ps,t,e [s
x]
uses e. Therefore, our shortest path trees rooted at s and t include a shortest path from s to x
and from t to y, and these paths were unaffected by the failure of e. Therefore, Ps,t,e has all edges
in the preserver, except possibly for (x, y). There are at most n edges on π(s, t), so there are at
most n edge faults for which we need to include a replacement path in our preserver. We can thus
complete the preserver by adding the single missing edge for each replacement path, and this costs
at most n edges. If the edge fault e does not lie on the included shortest path from s to t, then the
structure is trivially a preserver. Thus, we may assume that e is in π(s, t). We now claim that, for
some valid replacement path Ps,t,e protecting against the fault e, all but one (or all) of the edges
of Ps,t,e are in the preserver. To see this, we invoke Lemma 4.2: there is an edge (x, y) in Ps,t,e
such that no shortest path from s to x and no shortest path from t to y in G Ps,t,e [s
x] uses e.
Therefore, our shortest path trees rooted at s and t include a shortest path from s to x and from
t to y, and these paths were unaffected by the failure of e. Therefore, Ps,t,e has all edges in the
preserver, except possibly for (x, y). There are at most n edges on π(s, t), so there are at most n
edge faults for which we need to include a replacement path in our preserver. We can thus complete
the preserver by adding the single missing edge for each replacement path,, paying ≤ n edges.
With a trivial union bound, we get that any set P of node pairs can be preserved using
O(min(n|P |, n2 )) edges. It is natural to wonder if one can improve this union bound by doing
something slightly smarter in the construction.

Theorem 4.3. For any integer 1 ≤ p ≤ n2 , there exists an undirected weighted graph G and a set
P of p node pairs such that every 1-FT P -pairwise preserver of G contains Ω(min(np, n2 )) edges.
Proof. We construct our lower bound instance by adapting the construction in Lemma 3.3. First,
add a path of length n + 1 using edges of weight 1. Call the nodes on the path p1 , . . . , pn+1 . Next,
create n new nodes {vi }, and add an edge of weight 1 from pn+1 to each vi . Then, for each i ∈ [1, p],
add a new node xi to the graph, and connect xi to pi with an edge of weight 2(n − i) + 1. Finally,
for all i ∈ [1, p], j ∈ [1, n], add an edge of weight 1 between xi and vj . Define the pair set P to
be {s} × {vi | i ∈ [1, p]}. Note that the graph has Θ(n) nodes and Ω(n|P |) edges, because there
are exactly n|P | edges between the nodes {xi } and {vj }. We will complete the proof by arguing
that all edges in {xi } × {vj } must be kept in the preserver. Specifically, we claim that for any i, j,
the edge (xi , vj ) is needed to preserve the distance of the pair (s, vj ) ∈ P when the edge (pi , pi+1 )
faults. To see this, note that any path from s to vj must pass through some node xi , and we have
dist(s, xi ) = (i − 1) + 2(n − i) + 1 = 2n − i for any i. Since (pi , pi+1 ) has faulted, the path from s to
vj must intersect xi0 for some i0 ≤ i before it intersects xi00 for any i00 > i. Therefore, the shortest
s − vj path passes through xi , and thus uses (xi , vj ).
12

We show that the situation dramatically changes for f = 2.
Theorem 4.4. There exists an undirected weighted graph G and a single node pair (s, t) in this
graph such that every 2-FT (s, t) preserver of G requires Ω(n2 ) edges. The same lower bound holds
on the number of bits of space used by any exact distance sensitivity oracle in the same setting.
Proof. For the first claim, we construct our lower bound instance as follows. Build node disjoint
paths Ps = (s = s0 , s1 . . . , sn−1 ) and Pt = (t = t0 , t1 , . . . , tn−1 ) of n nodes each. All of the edges in
these paths have weight zero (or sufficiently small ε > 0 will do). Next, we add a complete bipartite
graph X × Y with edges of weight 1, where X = {x0 , . . . , xn−1 } and Y = {y0 , . . . , yn−1 } are new
node sets of size n each. Finally, for each i ∈ {0, . . . , n − 1}, we add edges (si , xi ) and (ti , yi ) of
weight n − i. See Fig. 2a for an illustration of this construction.
We now claim that every 2-FT s-t preserver must include all edges of the bipartite graph X ×Y .
In more detail, the edge (xi , yj ) is needed when the edges esi = (si , si+1 ) and etj = (tj , tj+1 ) fail.
Indeed, there is path of length n − i + n − j + 1 passing throw (xi , yj ) in G \ {esi , etj } and any other
s-t path has length at least n − i + n − j + 2. The first claim follows.
For the second claim, consider the same graph as before, but with possibly some missing edges
in X × Y . Consider any distance sensitivity oracle for this family of instances. By querying the s-t
distance for faults (esi , etj ), one obtains n − i + n − j + 1 iff the edge (xi , yj ) is present in the input
graph. This way it is possible to reconstruct the edges E 0 ⊆ X × Y in the input instance. Since
2
there are Ω(2n ) possible input instances, the size of the oracle has to be Ω(n2 ).
We next consider the case of directed graphs, and prove Theorem ??. We split its proof in the
next two lemmas. Let DP(n) describe the worst-case sparsity of a (non-FT) preserver of n node
pairs in a directed weighted graph. That is, for any directed weighted n-node graph G and set P
of |P | = n node pairs, there exists a distance preserver of G, P on at most DP(n) edges, yet there
exists a particular G, P for which every distance preserver has DP(n) edges.
Lemma 4.5. Given any s-t pair in a directed weighted graph, there is a 1-FT s-t preserver whose
sparsity is O(DP(n)).
Proof. Add a shortest path π(s, t) to the preserver, and note that we only need replacement paths
in our preserver for edge faults e on the path π(s, t). There are at most n − 1 such edges; thus, the
preserver is the union of at most n − 1 replacement paths. For each replacement path Ps,t,e , note
that the path is disjoint from π(s, t) only on one continuous subpath. Let a, b be the endpoints of
this subpath. Then Ps,t,e [a
b] is a shortest path in the graph G \ π(s, t), and all other edges in
Ps,t,e belong to π(s, t). Therefore, if we include in the preserver all edges in a shortest path from a
to b in G \ π(s, t), then we have included a valid replacement path protecting against the edge fault
e. By applying this logic to each of the n − 1 possible edge faults on π(s, t), we can protect against
all possible edge faults by building any preserver of n − 1 node pairs in the graph G \ π(s, t).
Lemma 4.6. There is a directed weighted graph G and a node pair s-t such that any 1-FT s-t
preserver requires Ω(DP(n)) edges.
Proof. Let K be a directed graph on O(n) nodes and nonnegative edge weights, and let P =
{(x1 , y1 ), ..., (xn , yn )} be a set of node pairs of size n such that the sparsest preserver of K, P has
Ω(f (n)) edges.
Add to K a directed path Y := (s → a1 → b1 → a2 → b2 → · · · → an → bn → t) on 2n + 2 new
nodes. All edges in Y have weight 0 (or sufficiently small ε > 0 will do). All other edge weights in
the graph will be nonnegative, so Y is the unique shortest path from s to t.
13

𝑠

𝐾

0
0

…
0

1

𝑦1

𝑥1

0

𝑎1

0

𝑏1

𝑛−2 𝑊

𝑠

𝑦2

𝑥2

𝑥𝑖

0

𝑦𝑖

𝑥𝑖

𝑦𝑛

𝑥𝑛

2𝑊

𝑛

𝑎2

0

𝑏2 … 𝑎𝑖

0

𝑏𝑖 … 𝑎𝑛

0

𝑏𝑛

0

𝑡

𝑦𝑗
1

0
0

…

𝑛

0

𝑡

(a) Lower bound example for single pair and
two faults. When the ith edge on the s-path
fails, the new shortest path to t must go
through xi . Similarly, when the jth edge
on the t-path fails, the shortest path to s
must go through yj . Hence, the shortest
path in G \ {ei , ej } uses the edge (xi , yj ).

(b) Lower bound construction for a single
pair in the directed weighted case. Here,
K is an arbitrary lower bound graph for
(non-FT) distance preservers of n pairs in
the directed weighted setting, which can be
modularly substituted in to our construction.

Figure 2: Lower bounds for weighted graphs.

Let M be the largest edge weight in K, and let W = M · n. Note that W is larger than the
weight of any shortest path in K. Now, for each i ∈ [1, n], add an edge from ai to xi of weight
(n − i)W and add an edge from yi to bi of weight iW . See Fig. 2b for an illustration This completes
the construction of G. There are O(n) nodes in G, and so it suffices to show that all edges in a
preserver of K, P must remain in a 1-FT s-t preserver for G.
Let (ai → bi ) be an edge on the path Y . If this edge faults, then the new shortest path from s
to t has the following general structure: the path travels from s to aj for some j ≤ i, then it travels
to xj , then it travels a shortest path from xj to yk (for some k ≥ i) in K, then it travels from yk
to bk , and finally it travels from bk to t. The length of this path is then
(n − j)W + distK (xj , yk ) + kW = nW + (k − j)W + distK (xj , yk ).
Suppose that k − j ≥ 1. Then the weight of the detour is at least (n + 1)W (as all distances in K
are nonnegative). On the other hand, if k = j (and hence = i), the weight of the detour is
nW + distK (xi , yk ) < (n + 1)W
because we have W > distK (xi , yk ). Thus, any valid replacement path Ps,t,(ai ,bi ) travels from s to
ai , then from ai to xi , then along some shortest path in K from xi to yi , then from yi to bi , and
finally from bi to t.
Hence, any 1-FT s-t preserver includes a shortest path from xi to yi in K for all i ∈ [1, n].
Therefore, the number of edges in this preserver is at least the optimal number of edges in a
preserver of K, P ; i.e. DP(n) edges. Since G has O(n) nodes, the theorem follows.

5

Open Problems

There are lots of open ends to be closed. Perhaps the main open problem is to resolve the current
gap for f -FT single-source preservers. Since the lower bound of Ω(n2−1/(f +1) ) edges given in [Par15]
has been shown to be tight for f ∈ [1, 2], it is reasonable to believe that this is the right bound
for f ≥ 3. Another interesting open question involves lower bounds for FT additive spanners. Our
14

lower-bounds are super linear only for f ≥ 2. The following basic question is still open though: is
there a lower bound of Ω(n3/2+ ) edges for some  ∈ (0, 1] for 2-additive spanners with one fault?
Whereas our lower bound machinery can be adapted to provide non trivial bounds for different
types of f -FT P -preservers (e.g., P = {s, t}, P = S × T , etc.), our upper bounds technique for
general f ≥ 2 is still limited to the sourcewise setting. Specifically, it is not clear how to construct
an f -FT S × S preservers other than taking the (perhaps wasteful) f -FT S-sourcewise preservers.
As suggested by our lower bounds, these questions are interesting already for a single pair.

15

References
[AB16]

A. Abboud and G. Bodwin. The 4/3 additive spanner exponent is tight. In STOC,
pages 351–361, 2016.

[ABP17]

Amir Abboud, Greg Bodwin, and Seth Pettie. A hierarchy of lower bounds for sublinear
additive spanners. In SODA, pages 568–576, 2017.

[ACIM99] D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and
shortest paths (without matrix multiplication). SIAM J. Comput., 28(4):1167–1181,
1999.
[ADD+ 93] I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J. Soares. On sparse spanners of weighted
graphs. Discrete & Computational Geometry, 9(1):81–100, 1993.
[BCPS15] G. Braunschvig, S. Chechik, D. Peleg, and A. Sealfon. Fault tolerant additive and (µ,
α)-spanners. Theor. Comput. Sci., 580:94–100, 2015.
[BCR16]

S. Baswana, K. Choudhary, and L. Roditty. Fault tolerant subgraph for single source
reachability: generic and optimal. In STOC, pages 509–518, 2016.

[BGG+ 15] D. Bilò, F. Grandoni, L. Gualà, S. Leucci, and G. Proietti. Improved purely additive
fault-tolerant spanners. In ESA, pages 167–178. 2015.
[BGLP14] D. Bilò, L. Gualà, S. Leucci, and G. Proietti. Fault-tolerant approximate shortest-path
trees. In ESA, pages 137–148. 2014.
[BK09]

Aaron Bernstein and David R. Karger. A nearly optimal oracle for avoiding failed
vertices and edges. In STOC, pages 101–110, 2009.

[Bod17a]

G. Bodwin. Linear size distance preservers. In SODA, 2017.

[Bod17b]

Greg Bodwin. Linear size distance preservers. In SODA, pages 600–615, 2017.

[BTMP05] S. Baswana, K. Telikepalli, K. Mehlhorn, and S. Pettie. New constructions of (alpha,
beta)-spanners and purely additive spanners. In SODA, pages 672–681, 2005.
[BW16]

G. Bodwin and V. Vassilevska Williams. Better distance preservers and additive spanners. In SODA, pages 855–872, 2016.

[CE06]

D. Coppersmith and M. Elkin. Sparse sourcewise and pairwise distance preservers.
SIAM Journal on Discrete Mathematics, 20(2):463–501, 2006.

[Che13]

S. Chechik. New additive spanners. In SODA, pages 498–512, 2013.

[CLPR09] S. Chechik, M. Langberg, D. Peleg, and L. Roditty. Fault-tolerant spanners for general
graphs. In STOC, pages 435–444, 2009.
[CP10]

S. Chechik and D. Peleg. Rigid and competitive fault tolerance for logical information
structures in networks. In Electrical and Electronics Engineers in Israel (IEEEI), 2010
IEEE 26th Convention of, pages 000024–000025. IEEE, 2010.

[CZ04]

A. Czumaj and H. Zhao. Fault-tolerant geometric spanners. Discrete & Computational
Geometry, 32(2):207–230, 2004.
16

[DK11]

M. Dinitz and R. Krauthgamer. Fault-tolerant spanners: better and simpler. In PODC,
pages 169–178, 2011.

[DP09]

R. Duan and S. Pettie. Dual-failure distance and connectivity oracles. In SODA, pages
506–515, 2009.

[DP17]

Ran Duan and Seth Pettie. Connectivity oracles for graphs subject to vertex failures.
In SODA, pages 490–509, 2017.

[DTCR08] C. Demetrescu, M. Thorup, R. A. Chowdhury, and V. Ramachandran. Oracles for
distances avoiding a failed node or link. SIAM Journal on Computing, 37(5):1299–
1318, 2008.
[EP04]

M. Elkin and D. Peleg. (1+epsilon, beta)-spanner constructions for general graphs.
SIAM J. Comput., 33(3):608–631, 2004.

[Erd63]

P. Erdös. Extremal problems in graph theory. Theory of Graphs and its Applications
(Proc. Sympos. Smolenice, 1963), pages 29–36, 1963.

[GW12]

F. Grandoni and V. Vassilevska Williams. Improved distance sensitivity oracles via fast
single-source replacement paths. In FOCS, pages 748–757, 2012.

[LNS02]

C. Levcopoulos, G. Narasimhan, and M. Smid. Improved algorithms for constructing
fault-tolerant spanners. Algorithmica, 32(1):144–156, 2002.

[Luk99]

T. Lukovszki. New results on fault tolerant geometric spanners. In Algorithms and Data
Structures, pages 193–204. Springer, 1999.

[MMG89] K. Malik, A. K. Mittal, and S. K. Gupta. The k most vital arcs in the shortest path
problem. Operations Research Letters, 8(4):223–227, 1989.
[Par14]

M. Parter. Vertex fault tolerant additive spanners. In Distributed Computing, pages
167–181. Springer, 2014.

[Par15]

M. Parter. Dual failure resilient BFS structure. In PODC, pages 481–490, 2015.

[Pet09]

S. Pettie. Low distortion spanners. ACM Transactions on Algorithms, 6(1), 2009.

[PP13]

M. Parter and D. Peleg. Sparse fault-tolerant BFS trees. In ESA, pages 779–790, 2013.

[PP14]

M. Parter and D. Peleg. Fault tolerant approximate BFS structures. In SODA, pages
1073–1092, 2014.

[RZ12]

L. Roditty and U. Zwick. Replacement paths and k simple shortest paths in unweighted
directed graphs. ACM Transactions on Algorithms, 8(4):33, 2012.

[TZ06]

M. Thorup and U. Zwick. Spanners and emulators with sublinear distance errors. In
SODA, pages 802–809, 2006.

[VW11]

V. Vassilevska Williams. Faster replacement paths. In SODA, pages 1337–1346. SIAM,
2011.

[Woo10]

D. P. Woodruff. Additive spanners in nearly quadratic time. In ICALP, pages 463–474,
2010.

[WY13]

O. Weimann and R. Yuster. Replacement paths and distance sensitivity oracles via fast
matrix multiplication. ACM Transactions on Algorithms, 9(2):14, 2013.
17

𝑑(ℓ ℎ − 1 + 3)

𝑟ℎ

(𝑑 − 1)(ℓ ℎ − 1 + 3)

𝑆ℎ

𝑣1

….

(𝑑 − 𝑗)(ℓ ℎ − 1 + 3)

𝑣𝑗

𝑇ℎ
𝐿(𝑇 ℎ )

….

ℓ ℎ − 1 + 3)

𝑠

𝑣𝑑−1

𝐿(𝑇 ℎ )

ℎ−1
𝑇𝑑−1

𝑇ℎ

𝑇𝑗ℎ−1

𝑡

𝑇1ℎ−1
𝑇0ℎ−1

(b) The graph S h used to provide a lower bound for
s-t pair and 1-additive stretch

(a) Structure of T h tree

𝑠
𝑠1

Ω( 𝑛/|𝑆|)

…

…
𝑡2

Ω( 𝑛/|𝑇|)

𝑡1

𝑇1ℎ

𝑠𝜎

𝑠2

𝑆1ℎ

𝑞

𝑡𝜎′

𝑡

ℎ
𝑇2𝑞

𝑆1

(d) The graph Sqh used to provide lower
(c) Lower bound for S × T preserver (and
bound for additive stretch β = 2q − 1 al1-additive) for the case f = 2
ready for a single pair s-t
Figure 3: Illustration of the lower bound constructions.

A

Tables
f -VFT (or EFT) Preservers
pairs P , f = 1
S-sourcewise
(unweighted)
(weighted)

Single pair s-t, f = 1
(weighted+directed)

Upper
Bound

e |S|1/2f · n2−1/2f )
O(f

O(min{n2 , n|P |})

O(DP (n)) = O(n3/2 )

New

New

New

Lower
Bound

Ω(|S|1/(f +1) · n2−1/(f +1) )

Ω(min{n2 , n|P |})

Ω(DP (n)) = Ω(n4/3 )

[Par15]

New

New

B
B.1

Omitted Details of Section 3
Properties of T h

We next prove Lemma 3.2.
Lemma B.1. `(h) = 3((d + 1)h − 1) and n(h) ≤ 32 (h + 1)(d + 1)h+1 .
Proof. Let us prove the first claim by induction on h. The claim is trivially true for h = 0. Next
suppose it holds up to h − 1 ≥ 0, and let us prove it for h. All the subtrees Tjh−1 used in the
18

construction of T h have the same height `(h − 1) which is 3((d + 1)h−1 − 1) by the inductive
hypothesis. The distance between rt(T h ) and rt(Tjh−1 ) is j + (d − j)(`(h − 1) + 3) which is a
decreasing function of j. In particular, the maximum such distance is the one to rt(T0h−1 ), which
is d(`(h − 1) + 3). We conclude that


`(h) = `(h − 1) + d(`(h − 1) + 3) = 3d + (d + 1)3 (d + 1)h−1 − 1 = 3(d + 1)h − 3.
The second claim is trivially true for h = 0. The number of nodes in T h is given by d times the
number of nodes in T h−1 , plus the sum of the lengths of the paths connecting each vj to rt(Tjh−1 ),
i.e.
n(h) = d · n(h − 1) +

d−1
X

f irst

(d − j)(`(h − 1) + 3) claim
= d · n(h − 1) + 3(d + 1)h−1

j=0
Induct.
hypoth.

≤

d(d + 1)
2

3
3
3
3
d · h(d + 1)h + d(d + 1)h = (h + 1)d(d + 1)h ≤ (h + 1)(d + 1)h+1 .
2
2
2
2

We next need a more technical lemma which will be useful to analyze the stretch. An easy
inductive proof shows that |L(T h )| = dh . It is convenient to sort these leaves from left to right
using the following inductive process. The base case is that T 0 has a unique leaf (the root) which
obviously has a unique ordering. For the inductive step, given the sorting of the leaves of T h−1 ,
the sorting for T h is achieved by placing all the leaves in the subtree Tjh−1 to the left of the leaves
h−1
of the subtree Tj+1
, j = 0, . . . , d − 2 (the leaves of each Tjh−1 are then sorted recursively). Given
this sorting, we will name the leaves of T H (from left to right) `h0 , . . . , `hdh −1 .
For each leaf `hj , we next recursively define a subset of at most h (faulty) edges Fjh . Intuitively,
these are edges that we can remove to make `hj the closest leaf to the root. We let Fj0 = ∅. Suppose
that `hj is the r-th leaf from left to right of Tth−1 (in zero-based notation). Then Fjh is given by the
edges of type Frh−1 in Tth−1 , plus edge (vt , vt+1 ) if t < d − 1. Note that obviously |Fjh | ≤ h.
Lemma B.2. One has that `hj is the leaf at minimum finite distance d0 := distT h −F h (rt(T h ), `hj )
j

from rt(T h ) in T h − Fjh , and any other leaf in L(T h ) − {`hj } is at distance at least d0 + 2 from
rt(T h ).
Proof. Once again the proof is by induction. Let rh := rt(T h ). The claim is trivially true for h = 0
since there is a unique leaf `00 = r0 . Next assume the claim is true up to h − 1 ≥ 0, and consider
T h . Consider any leaf `hj , and with the same notation as before assume that it is the r-th leaf from
left to right of Tth−1 . Observe that by removing edge (vt , vt+1 ) we disconnect from rh all nodes
in subtrees Tth−1
with t0 > t. In particular the distances from rh to the leaves of those subtrees
0
becomes unbounded. Next consider a leaf `0 in a tree Tth−1
with t0 < t. By construction we have
0
that
distG−F h (rh , `0 ) ≥ distG (rh , `0 )
j

≥ distG (rh , rt(Tth−1
))
0
= t0 + (d − t0 )(`(h − 1) + 3)
≥ (t − 1) + (d − t + 1)(`(h − 1) + 3)
= t + (d − t)(`(h − 1) + 3) + `(h − 1) + 2.
19

On the other hand, any leaf in L(Tth−1 ) which is still connected to rt(Tth−1 ) has distance at most
t + (d − t)(`(h − 1) + 3) + `(h − 1) from rh . Recall that we are removing the edges of type Frh−1 from
Tth−1 . Note also that `hj corresponds to leaf `h−1
in Tth−1 . Hence, by the inductive hypothesis, `hj
r
is the leaf of Tth−1 at minimum finite distance d0 from rth−1 , and any other such leaf is at distance
at least d0 + 2 from rth−1 . The claim follows.
Proof of Lemma 3.2. Claim 1 is given by Lemma B.1, Claim 2 by a trivial induction, and Claim 3
by Lemma B.2.

B.2

Improvement with Preserver Lower Bounds

We next prove Theorem 3.4. We need the following technical lemma.
Lemma B.3 ( [Bod17a]). For all n, there is an undirected unweighted bipartite graph G = (V, E) on
n nodes and Ω(n11/10−o(1) ) edges, as well as disjoint node subsets S, T ⊆ V with |S| = |T | = Θ(n1/2 )
such that the following properties hold:
• For each edge e ∈ E, there is a pair of nodes s ∈ S, t ∈ T with dist(s, t) = L (for some
parameter L) such that every shortest (s, t) path includes e.
• For all s ∈ S, t ∈ T , we have dist(s, t) ≥ L.
The construction for Theorem 3.4 proceeds as follows. By Lemma B.1, the number of leaves in
T is ` = Θ(d) and the number of nodes in T 1 is n = Θ(d2 ), so we have ` = Θ(n1/2 ). As before, let
Ts , Tt be copies of T 1 rooted at s, t respectively. Now, let H be a graph drawn from Lemma B.3,
with node subsets S, T , where the number of nodes nH is chosen such that |S| = |T | = `(s) = `(t).
We add a copy of H to the graph Ts ∪ Tt , where `(s) is used as the node set S, `(t) is used as the
node set T , and O(n) new nodes are introduced to serve as the remaining nodes in H. Note that
the new graph G = Ts ∪ Tt ∪ H now has N = Θ(n) nodes, so it (still) has N 11/10−o(1) edges in its
internal copy of H.
1

Lemma B.4. In G, we have:
• For each edge e in the internal copy of H, there exist nodes u ∈ `(s) = S, v ∈ `(t) = T with
dist(u, v) = L such that every shortest (u, v) path (in G) includes e.
• For all u ∈ `(s) = S, v ∈ `(t) = T , we have dist(u, v) ≥ L.
Proof. First, we observe that if any shortest (u, v) path π(u, v) in G contains a node x not in the
internal copy of H, then we have dist(u, v) ≥ L + 1. To see this, note that by construction any
(x, v) path must contain a subpath π(u0 , v 0 ) ⊆ H between nodes u0 ∈ S, v 0 ∈ T . By Lemma B.3
this subpath has length at least L. Since the path π(u, v) contains x ∈
/ π(u0 , v 0 ), we then have
|π(u, v)| ≥ L + 1.
The second point in this lemma is now immediate: if π(u, v) is contained in H then we have
dist(u, v) ≥ L from Lemma B.3; if π(u, v) is not contained in H then we have dist(u, v) ≥ L + 1
from the above argument. For the first point, note that by Lemma B.3, there is a pair u ∈ S, v ∈ T
such that distH (u, v) = L and every shortest (u, v) path in H includes e. Since we then have
distG (u, v) ≤ L, by the above it follows that π(u, v) is contained in H, and the lemma follows.
We can now show:

20

Proof of Theorem 3.4. Let e be any edge in the internal copy of H in G. By Lemma B.4, there is a
pair of nodes u ∈ `(s) = S, v ∈ `(t) = T such that every (u, v) shortest path in G includes e. Also,
by Lemma B.2, there are faults f1 ∈ Ts , f2 ∈ Tt such that u is the leaf of Ts at minimum distance
d0s from s in Ts \ {f1 }, and v is the leaf of Tt at minimum distance d0t from t in Tt \ {f2 }.
Thus, under fault set {f1 , f2 }, we have
distG\{f1 ,f2 } (s, t) ≤ d0s + L + d0t
since one possible (s, t) path is obtained by walking a shortest path from s to u, then from u to v,
then from v to t. Moreover, any (s, t) path Q in G \ {f1 , f2 } that does not include u (or v) must
include some other leaf u0 6= u ∈ `(s), so it has length at least
|Q| ≥ distG\{f1 ,f2 } (s, u0 ) + distG\{f1 ,f2 } (u0 , v 0 ) + distG\{f1 ,f2 } (v 0 , t)
(for some leaf v 0 ∈ Tt , possibly equal to v). By Lemmas B.2 and B.4, this implies
|Q| ≥ (d0s + 2) + L + d0t > distG\{f1 ,f2 } (s, t).
Therefore Q is a non-shortest path, and so every shortest (s, t) path in G \ {f1 , f2 } includes nodes
u and v, and so (by Lemma B.4) it includes the edge e. We then cannot remove the edge e without
destroying all shortest (s, t) shortest paths in G \ {f1 , f2 }, so all N 11/10−o(1) edges in the internal
copy of H must be kept in any 2-FT distance preserver of (s, t).
Remark B.5. It is natural to expect that a similar improvement to the lower bound may be possible
for h > 1; that is, we could imagine again augmenting the bipartite core with a subset preserver
lower bound. While it is conceivable that this technique may eventually be possible, it currently does
not work: for h > 1 we have `(s) = Ω(n(s)2/3 ), and it is currently open to exhibit a lower bound
G = (V, E), S for subset preservers in which |S| = Ω(n2/3 ) and |E| = ω(|S|2 ). In other words, for
h > 1, the current best known subset preserver lower bound that could be used is just a complete
bipartite graph, and so we can do no better than the construction using bipartite cores.

B.3

Improvement with Spanner Lower Bounds

We next prove Theorem 3.5. Our new “inner graph” that replaces the bipartite core is drawn from
the following lemma7 :
Lemma B.6 ( [AB16]). There are absolute constants ε, δ > 0, a family of n-node graphs G =
(V, E), node subsets S, T ⊆ V of size |S| = |T | = Θ(n1/2−δ ), and a set P ⊆ S × T such that any
subgraph H ⊆ G on o(n1+ε ) edges has distH (s, t) > distG (s, t)+nδ for some (s, t) ∈ P . Moreover,
we have distG (s, t) = L for all (s, t) ∈ P , and distG (s, t) ≥ L for all (s, t) ∈ S × T .
We now describe our construction. First, as before, we take trees Ts , Tt which are copies of T 1
rooted at s, t respectively. We now label leaves of Ts (and Tt ) as good leaves or bad leaves using the
following iterative process. Arbitrarily select a leaf ` and label it a good leaf. Next, for all leaves
`0 satisfying distTs (s, `0 ) ∈ [distTs (s, `) − nδ , distTs (s, `) + nδ ], we label `0 a bad leaf. We then
arbitrarily select another good leaf from among the unlabelled leaves, and repeat until all leaves
have a label. Note that we have Θ(n1/2 ) leaves of Ts ; by construction distTs (s, `) 6= distTs (s, `0 )
for any two leaves `, `0 , and so the total number of good leaves is Θ(n1/2−δ ). Note:
7

The result proved in [AB16] is more general than this one; the parameters have been instantiated in this statement
to suit our purposes.

21

Lemma B.7 (Compare to Lemma B.2). One has that any good leaf `hj is the leaf at minimum
finite distance d0 := distT h −F h (rt(T h ), `hj ) from rt(T h ) in T h − Fjh , and any other good leaf in
j

L(T h ) − {`hj } is at distance at least d0 + nδ from rt(T h ).
Proof. Immediate from Lemma B.2 and the selection of good leaves.
We insert a graph H drawn from Lemma B.6 into the graph Ts ∪ Tt , using the good leaves of
Ts as the set S and the good leaves of Tt as the set T (as before, all other nodes in H are newly
added to the graph in this step). Note that the final graph Ts ∪ H ∪ Tt still has N = Θ(n) nodes.
This completes the construction.
We now argue correctness, i.e. we show that one cannot sparsify the final graph to o(N 1+ε )
edges without introducing +nδ error in the s-t distance for some well-chosen set of two faults. The
proof is essentially identical to the one used above, but we repeat it for completeness.
Proof of Theorem 3.5. Let G0 = (V, E 0 ) be a subgraph of the final graph G = (V, E) with |E 0 | =
o(N 1+ε ) edges. By Lemma B.6, there is a pair of good leaves (`s , `t ) ∈ P such that
distG0 [H] (`s , `t ) > L + nδ
(where G0 [H] denotes the copy of H in G0 ). By Lemma B.7, there are faults f1 , f2 such that `s is
the leaf at minimum distance d0s from s, `t is the leaf at minimum distance d0t from t, (`s , `t ) ∈ P ,
and the distance from s (resp. t) to any other good leaf `0s 6= `s (resp. `0t 6= `t ) is at least d0s + nδ
(resp. d0t + nδ ). Thus, we have
distG\{f1 ,f2 } (s, t) ≤ d0s + L + d0t .
We now lower bound this distance in G0 . As before, there are two cases: either the shortest (s, t)
path in G0 traverses a shortest (`s , `t ) path in G0 [H], or it does not. If so, then we have
distG0 \{f1 ,f2 } (s, t) ≥ d0s + (L + nδ ) + d0t ≥ distG\{f1 ,f2 } (s, t) + nδ
and so G0 is not a 2-FT +nδ − 1 (s, t) preserver of G, and the theorem follows. Otherwise, if the
shortest (s, t) path in G0 does not traverse a shortest (`s , `t ) path in G0 [H], then by construction it
passes through (w.l.o.g.) some good leaf `0s 6= `s ∈ Ts and `0t ∈ Ts (where `0t is possibly equal to `t ).
We then have
distG0 \{f1 ,f2 } (s, t) ≥ distG0 \{f1 ,f2 } (s, `0s ) + distG\{f1 ,f2 } (`0s , `0t ) + distG0 \{f1 ,f2 } (`0t , t)
≥ (d0s + nδ ) + L + d0t
≥ distG\{f1 ,f2 } (s, t) + nδ
and the theorem follows.
Finally, by tolerating one additional fault, we can obtain a strong incompressibility result, hence
proving Theorem 3.6: The proof is nearly identical to the above, but there are two key differences.
First, we use unbalanced trees: Ts is a copy of T 1 while Tt is a copy of T 2 . Hence, there are three
total faults in the sets F`ss ∪ F`tt used to “select” the appropriate leaves s, t. We define good leaves
exactly as before. We use a slightly different lemma for our inner graph (which is proved using the
same construction):

22

Lemma B.8 ( [AB16]). There is an absolute constant δ > 0, a family of n-node graphs G = (V, E),
node subsets S, T ⊆ V of size |S| = Θ(n1/2−δ ), |T | = Θ(n2/3−δ ), and a set P ⊆ S × T of size
|P | = |S||T |n−o(1) with the following property: for each pair (s, t) ∈ P , we may assign a set of
edges in G to p such that (1) no edge is assigned to two or more pairs, and (2) if all edges assigned
to a pair (s, t) are removed from G, then dist( s, t) increases by +nδ . Moreover, dist(s, t) = L for
all (s, t) ∈ P , and dist(s, t) ≥ L for all (s, t) ∈ S × T .
Proof of Theorem 3.6. Let G, P be a graph and pair set drawn from Lemma B.8. Define a family
of 2|P | subgraphs by independently keeping or removing all edges assigned to each pair in P . We
will argue that any nδ/2 -additive distance sensitivity oracle must use a different representation for
each such subgraph, and thus, |P | = Ω(n1+ε ) bits of space are required in the worst case.
Suppose towards a contradiction that a distance sensitivity oracle uses the same space representation for two such subgraphs G1 , G2 , and let (`s , `t ) ∈ P be a pair for which its owned edges
are kept in G1 but removed in G2 . By an identical argument to the one used in Theorem 3.5, we
have
distG1 \{f1 ,f2 ,f3 } (s, t) ≤ d0s + L + d0t
for fault set {f1 , f2 , f3 } = F`ss ∪ F`tt (where d0s , d0t are defined exactly as before). Meanwhile, also by
the same argument used in Theorem 3.5, we have
distG2 \{f1 ,f2 ,f3 } (s, t) ≥ d0s + L + d0t + nδ ≥ distG1 \{f1 ,f2 ,f3 } (s, t) + nδ .
Since G1 , G2 are stored identically by the distance sensitivity oracle, it must answer the query
{f1 , f2 , f3 } identically for both graphs. However, since the right answer differs by +nδ from G1 to
G2 , it follows that the oracle will have at least +nδ /2 − 1 error on one of the two instances.

B.4

Lower Bound for S × T Preservers

Theorem B.9. For every positive integer f , there exists a graph G = (V, E) and subsets S, T ⊆
V , such that every (2f )-FT 1-additive S × T spanner (hence S × T preserver) of G has size
Ω(|S|1/(f +1) · |T |1/(f +1) · (n/f )2−2/(f +1) ).
Proof. The graph G is constructed as follows (see also Figure 3c). For each si ∈ S, we construct a
copy Tsi of T f rooted at si with size parameter

dS =

n
3(f + 1)|S|



1
f +1

− 1.

Similarly, for each tj ∈ T , we construct a copy Ttj of T f rooted at tj with size parameter

dT =

n
3(f + 1)|T |



1
f +1

− 1.

Finally, we add a complete bipartite graph between the leaves of each Tsfi and the leaves of each
Ttfj . We call the edges of the last type the bipartite core of G.
Note that by Lemma B.1 the total number of nodes is n. Furthermore, the bipartite core has
size


f
 f +1
 2− 2 !

2
f +1
1
1
n
f f
 = Ω |S| f +1 |T | f +1 n
|S| |T | dS dT = Ω |S| |T |
9(f + 1)2 |S||T |
f
23

The rest of the proof follows along the same line as in Lemma 3.3: given any edge e = (`si , `tj )
between a leaf `si of Tsi and a leaf `tj of Ttj , removing e would cause an increase of the stretch
between si and tj by at least an additive 2 for a proper choice of f faults in both Tsi and Ttj .

24

