Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier
Hung Le, Shay Solomon, Cuong V. Than · 2023
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-F T)$ 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 90 s. For low-dimensional Euclidean metrics, Czumaj and Zhao in SoCG’03 [CZ03] showed that the optimal guarantees $O(f n), O(f)$ and $O\left(f^{2}\right)$ on the size, degree and lightness of f-FT spanners can be achieved via a greedy algorithm, which naïvely runs in $O\left(n^{3}\right) \cdot 2^{O(f)}$ time.$^{1}$ An earlier construction, by Levcopoulos et al. [LNS98] from STOC’98, has a faster running time of $O(n \log n)+n 2^{O(f)}$, but has a slack of $2^{\Omega(f)}$ in all the three involved parameters. 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: Any construction (other than [CZ03]) has lightness either $2^{\Omega(f)}$ or $\Omega(\log n)$. 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 $\Omega(\log n)$ since they are built on the net-tree spanner, which is induced by a hierarchical net-tree of lightness $\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\gt0$, and any integer $1 \le \log f n\le + {nfn}-)$, an2, our construction provides,-spanner with within time $O(n$ size $O (fn)$, degree $O(f)$ and lightness $O(f^{2})$. To break the $\Omega (\log n)$ lightness barrier, we introduce a new geometric object — the light net-forest. Like the net-tree, the light net-forest is induced by a hierarchy of nets. However, to ensure small lightness, the light net-forest is inherently less “well-connected” than the net-tree, which, in turn, makes the task of achieving fault-tolerance significantly more challenging. Further, to achieve the optimal degree (and size) together with optimal lightness, and to do so within the optimal running time — we overcome several highly nontrivial technical challenges.