Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the $\mathrm{\Omega }(\log n)$ Lightness Barrier

An essential requirement of spanners in many applications is to be fault-tolerant: a $(1+\epsilon )$-spanner of a metric space is called (vertex) $f$-fault-tolerant ($f$-FT) if it remains a $(1+\epsilon )$-spanner (for the non-faulty points) when up to $f$ faulty points are removed from the spanner. Fault-tolerant (FT) spanners for Euclidean and doubling metrics have been extensively studied since the 90s. For low-dimensional Euclidean metrics, Czumaj and Zhao in SoCG’03 [CZ03] showed that the optimal guarantees $O(fn)$, $O(f)$ and $O(f^2)$ on the size, degree and lightness of $f$-FT spanners can be achieved via a greedy algorithm, which naïvely runs in $O(n^3)\cdot 2^{O(f)}$ time. The question of whether the optimal bounds of [CZ03] can be achieved via a fast construction has remained elusive, with the lightness parameter being the bottleneck. Moreover, in the wider family of doubling metrics, it is not even clear whether there exists an $f$-FT spanner with lightness that depends solely on $f$ (even exponentially): all existing constructions have lightness $\mathrm{\Omega }(\log n)$ since they are built on the net-tree spanner, which is induced by a hierarchical net-tree of lightness $\mathrm{\Omega }(\log n)$. In this paper we settle in the affirmative these longstanding open questions. Specifically, we design a construction of $f$-FT spanners that is optimal with respect to all the involved parameters (size, degree, lightness and running time): For any $n$-point doubling metric, any $\epsilon >0$, and any integer $1\le f\le n-2$, our construction provides, within time $O(n\log n+fn)$, an $f$-FT $(1+\epsilon )$-spanner with size $O(fn)$, degree $O(f)$ and lightness $O(f^2)$.