Metric and Geometric Spanners that are Resilient to Degree-Bounded Edge Faults

Let H be an edge-weighted graph, and let G be a subgraph of H. We say that G is an f-fault-tolerant t-spanner for H, if the following is true for any subset F of at most f edges of G: For any two vertices p and q, the shortest-path distance between p and q in the graph G F is at most t times the shortest-path distance between p and q in the graph H F. Recently, Bodwin, Haeupler, and Parter generalized this notion to the case when F can be any set of edges in G, as long as the maximum degree of F is at most f. They gave constructions for general graphs H. We first consider the case when H is a complete graph whose vertex set is an arbitrary metric space. We show that if this metric space contains a t-spanner with m edges, then it also contains a graph G with O (fm) edges, that is resilient to edge faults of maximum degree f and has stretch factor O (ft). Next, we consider the case when H is a complete graph whose vertex set is a metric space that admits a well-separated pair decomposition. We show that, if the metric space has such a decomposition of size m, then it contains a graph with at most (2f+1) ² m edges, that is resilient to edge faults of maximum degree f and has stretch factor at most 1+, for any given > 0. For example, if the vertex set is a set of n points in Rᵈ (d being a constant) or a set of n points in a metric space of bounded doubling dimension, then the spanner has O (f² n) edges. Finally, for the case when H is a complete graph on n points in Rᵈ, we show how natural variants of the Yao- and -graphs lead to graphs with O (fn) edges, that are resilient to edge faults of maximum degree f and have stretch factor at most 1+, for any given > 0.