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

Abstract

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\setminus F$ is at most $t$ times the shortest-path distance between $p$ and $q$ in the graph $H\setminus 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{)}^{2}m$ edges, that is resilient to edge faults of maximum degree $f$ and has stretch factor at most $1+\epsilon$, for any given $\epsilon >0$. For example, if the vertex set is a set of $n$ points in ${\mathbb{R}}^d$ ($d$ being a constant) or a set of $n$ points in a metric space of bounded doubling dimension, then the spanner has $O(f^{2}n)$ edges. Finally, for the case when $H$ is a complete graph on $n$ points in ${\mathbb{R}}^d$, we show how natural variants of the Yao- and $\Theta$-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+\epsilon$, for any given $\epsilon >0$.

27 pages