arXiv preprint ·
New Fault-Tolerant $(α,β)$-Spanners
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We present new constructions of vertex fault-tolerant (VFT) $(α,β)$-spanners with substantially improved size bounds. Given a bound $f$ on the number of vertex faults, an $f$-VFT $(α,β)$-spanner is a subgraph of $G$ that preserves an $(α,β)$-spanner of $G- F$ for every fault set $F \subseteq V$ with $|F| \le f$. Most existing constructions of VFT $(α,β)$-spanners rely on a black-box sampling technique that incurs an exponential blow-up compared to their non-fault-tolerant counterparts. We develop two independent techniques for constructing $f$-VFT $(α,β)$-spanners that improve the dependence on $f$, reducing it to polynomial overhead. For every unweighted graph $G=(V,E)$ on $n$ vertices, stretch parameter $k$, and fault parameter $f$, we show: (i) $f$-VFT $(O_ε(k^ε), O_ε(k))$-spanners with $\tilde{O}(f^{exp(1/ε)}\cdot n^{1+1/k})$ edges for any $ε\in (0,1)$. For any fixed constant $ε$, this introduces a $poly(f)$ overhead compared to the non-faulty constructions of [Ben-Levy and Parter, SODA 2020] and [Chechik and Lifshitz, SODA 2026]. (ii) For any $δ\in (0,1)$, an $f$-VFT $\left(O_δ(\sqrt{k}),O_δ(k) \right)$-spanner of size $\tilde{O}(f^{1+δ} \cdot n^{1+\frac{1}{k}})$. Hence, it incurs a size overhead of only $f^{1+δ}$ compared to the above-mentioned non-faulty analogs. (iii) $f$-VFT $(k,k-1)$ spanner of size $O(k^3 \cdot f \cdot n^{1+\frac{1}{k}})$, nearly matching the lower bound $Ω(f^{1-\frac{1}{k}}n^{1+\frac{1}{k}})$ known for $f$-VFT $(2k-1,0)$ spanners by [Bodwin et al., SODA 2018]. The first result is obtained via a new adaptation of the Baswana--Sen framework to the VFT $(α,β)$ setting. The other two bounds follow from a highly involved analysis of a natural extension of the fault-tolerant greedy spanner.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Approximation algorithms for identical parallel machine scheduling with assignment costs
A Nearly Optimal Min-Cut Algorithm for Dynamic Streams
A Factor-6 Truthful-in-Expectation Mechanism for Cascade Position Auctions
Bicriteria Approximate Navigable Graphs in General Metrics
Engineering Lightweight Burrows-Wheeler Transform Construction on the GPU via Prefix-Free Parsing
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.