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 \setminus F$ is at most $t$ times the shortest-path distance between $p$ and $q$ in the graph $H \setminus F$. The value of $t$ is called the stretch factor. Numerous results are known for constructing such spanners, both for general graphs $H$ and for complete graphs $H$ whose vertex set is a set of points in $\mathbb{R}^d$ or in a metric space of bounded doubling dimension. Bodwin, Haeupler, and Parter [SODA 2024] 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$. For example, if $f=1$, then $F$ can be a perfect matching in $G$. They gave constructions for general graphs $H$. We present three new results for constructing spanners that are resilient to edge faults of maximum degree $f$. 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 at most $(4f-1)m$ edges, that is resilient to edge faults of maximum degree $f$ and has stretch factor $O(ft)$. We also give an example for which our construction has stretch factor $\Omega(ft)$. If $f=1$, the graph $G$ has at most $3m$ edges and its stretch factor is at most $3t$. For this case, we give an example for which $G$ has stretch factor arbitrarily close to $3t$. 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+\varepsilon$, for any given $\varepsilon > 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+\varepsilon$, for any given $\varepsilon > 0$.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.