PaperlayerView exact revision on arXiv

Source-linked AI summary

New Fault-Tolerant $(\alpha,\beta)$-Spanners

Merav Parter, Elizaveta Popova, Elad Tzalik

arXiv:2610.33934v1cs.DS

TL;DR

The paper studies how to preserve (α, β)-spanner guarantees under vertex failures, a setting where stretch must be maintained over entire paths. It extends two approaches for fault-tolerant multiplicative spanners to this setting, obtaining polynomial fault-dependent size bounds, including an (O(k, k−1)) stretch construction that nearly matches a known lower bound.

  • Problem

    The goal is to preserve (α, β) stretch guarantees even after up to f vertex failures, while ensuring stretch over entire paths rather than local edge conditions.

    Source: §1 · pp. 3–4

  • Method

    The paper extends two distinct approaches used for fault-tolerant multiplicative spanners to the (α, β) setting, with more involved arguments.

    Source: §1 · p. 4

  • Results

    For fixed ε, the paper gives an f-VFT (O(k^ε), O(k))-spanner with poly(f) · n^(1+1/k) edges; it also gives an f-VFT (k, k−1) spanner with O(f · k^3 · n^(1+1/k)) edges, nearly matching the Ω(f^(1−1/k)n^(1+1/k)) lower bound for f-VFT (2k−1, 0)-spanners.

    Source: §1 · pp. 4–5

  • Takeaways & Limitations

    The robust greedy clusters yield spanners with almost linear dependence on the number of faults.

    Source: §1 · p. 4

    Generally, fault-tolerant (α, β) spanners with α = o(k) remain an open problem.

    Source: §1 · p. 5

Abstract

from arXiv · show

We present new constructions of vertex fault-tolerant (VFT) $(\alpha,\beta)$-spanners with substantially improved size bounds. Given a bound $f$ on the number of vertex faults, an $f$-VFT $(\alpha,\beta)$-spanner is a subgraph of $G$ that preserves an $(\alpha,\beta)$-spanner of $G- F$ for every fault set $F \subseteq V$ with $|F| \le f$. Most existing constructions of VFT $(\alpha,\beta)$-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 $(\alpha,\beta)$-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_{\epsilon}(k^{\epsilon}), O_{\epsilon}(k))$-spanners with $\tilde{O}(f^{exp(1/\epsilon)}\cdot n^{1+1/k})$ edges for any $\epsilon \in (0,1)$. For any fixed constant $\epsilon$, 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 $\delta \in (0,1)$, an $f$-VFT $\left(O_{\delta}(\sqrt{k}),O_{\delta}(k) \right)$-spanner of size $\tilde{O}(f^{1+\delta} \cdot n^{1+\frac{1}{k}})$. Hence, it incurs a size overhead of only $f^{1+\delta}$ 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 $\Omega(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 $(\alpha,\beta)$ setting. The other two bounds follow from a highly involved analysis of a natural extension of the fault-tolerant greedy spanner.

1 Introduction

The paper addresses the exponential overhead of existing fault-tolerant sampling approaches for preserving additive spanner guarantees under vertex failures. It extends Baswana–Sen and greedy-spanner techniques, obtaining improved size bounds and identifying robust clusters as a key feature of the greedy analysis.

1 Introduction

  • For fixed ε ∈ (0, 1), the Baswana–Sen-type construction gives f-VFT (O(k^ε), O(k))-spanners with poly(f) · n^1+1/k edges.It circumvents the exponential-in-min{f, β/α} barrier of FT-sampling and offers a simpler alternative to, at the cost of slightly weaker size bounds.Source: §1 · p. 4
  • The greedy analysis couples its process with clustering to produce well-spread paths from vertices to centers, with clusters tolerating adversarial and random faults.The paper contrasts these clusters with, whose clusters guarantee at least one surviving path after up to f vertex failures.Source: §1 · p. 4
  • For any fixed constant δ > 0, the cited f-VFT spanner has ˜O(f^(1+δ) · n^(1+1/k)) edges.Source: §1 · p. 4
  • The greedy approach has inefficient running time because it scans all k-long paths; for k = O(log(n)), the modified greedy analysis is quasi-polynomial in n.The paper leaves improving the algorithm's running time as an open direction.Source: §1 · p. 4
  • Fault-tolerant (α, β)-spanners with α = o(k) remain an open problem, as do fault-tolerant analogues of several recent non-faulty constructions.The paper specifically points to guarantees for all distances d ≤ k and to (1 + ε, β)-spanners.Source: §1 · p. 5
  • O(f · k^3 · n^1+1/k) edges suffice for an f-VFT (k, k −1) spanner, nearly matching the Ω(f^1−1/k n^1+1/k) lower bound for f-VFT (2k −1, 0)-spanners.The result concerns small-locality spanners, which promise stretch k for vertex pairs at graph distance 2.Source: §1 · p. 5

2 Technical Overview

The technical overview contrasts classical fault-tolerant sampling, which can incur exponential size overhead, with Baswana–Sen-based and greedy constructions designed to improve dependence on faults. It previews replacement-path collections and stronger cluster/path structures, including guarantees that bound path additions through structural and distribution properties and robust connections among centers.

2.1 The Classical Approach to VFT (α, β) Spanners

  • The classical black-box method applies a fault-free spanner construction to replacement-path-covering subgraphs, but its size bound has exponential dependence on k or f.Replacement Path Covering requires that each short replacement path avoid the faults and be contained in some subgraph of the collection.Source: §2.1 · p. 6

2.2 A Baswana-Sen Type VFT (α, β) Spanner

  • Oversampling cluster centers lets the Baswana–Sen approach implement virtual-graph steps across (3√k, f)-replacement-path-covering subgraphs, yielding polynomial dependence on f.The construction adapts to general (Oε(k^ε), Oε(k))-spanners through repeated Baswana–Sen steps on virtual cluster graphs, where each step's edge count depends on the number of clusters rather than all vertices.Source: §2.2 · pp. 7–8
  • For clustered vertices at distance x, centers are within 3r; thus L = 3r is crucial to guarantee kε stretch, and this factor drives super-exponential dependence on ε in the final size bound.The non-faulty construction applies (1/ε) Baswana–Sen iterations to a virtual cluster graph, with each step’s edge count depending on clusters rather than vertices.Source: §2.2 · pp. 8–9

2.3 Greedy VFT (α, β)-Spanners

  • The greedy approach separates added paths into local-connectivity paths L and global paths G, with one greedy path able to serve many virtual center-pair edges.Its implicit fault-tolerant clusters are stronger than those of [Par22], and the approach optimizes the dependence on f; bounding G requires analyzing connectivity at scales up to r.Source: §2.2 · p. 7, §2.3 · pp. 9–10

2.3.1 Bounding L

  • The path system’s certificates and fault-tolerant distribution yield |L| = ˜O(Dn); the multiplicative greedy VFT-(2k−1) spanner has size O(k^3 f^(1−1/k)n^(1+1/k)), an O(k^3) factor above [BP19].The analysis relies on interdependent path-system properties, including well-distributed paths and pairwise parks.Source: §2.3.1 · pp. 10–11

2.3.2 Bounding G

  • Each path in G can improve connectivity for many center pairs at once; spreadness yields robust-sunflower connections that persist with constant probability even under massive random failures.The failure regime independently removes each vertex with probability close to 1, and the overview contrasts this robustness with FT clustering that handles adversarial faults but not massive random failures.Source: §2.3.2 · pp. 12–13

2.3.3 The Robust CLFT Process

  • The robust CLFT process represents greedy path additions as collections of center-to-center edges with vertex lists, then uses robust-sunflower structure to bound the number of rounds and thus |G|.Its analysis extends blocking-set size bounds to collections of edges forming a robust sunflower, with only negligible loss in parameters.Source: §2.3.3 · pp. 13–14
  • Unlike [PPST25]’s explicit path-collection construction and exp(k^2) size overhead, this approach obtains implicit collections and poly(k) overhead; unlike [PT26], it avoids a black-box reduction to non-faulty greedy spanners.The overview identifies evolving robust path systems, center interactions modeled by robust CLFT, and tight process analysis as tools tailored to fault tolerance.Source: §2.3.3 · p. 15

2.4 Organization of the Paper

  • The paper develops the VFT (Oε(k^ε), Oε(k)) construction in Section 3, the Oδ(√k), Oδ(k) construction of size ˜O(f^(1+δ)n^(1+1/k)) in Section 5, and VFT (k, k−1) spanners in Section 6.Section 6 uses a different analysis of the paths added by the greedy algorithm and is independent of Section 5.Source: §2.4 · pp. 15–16

3 VFT (kϵ, Oϵ(k))-Spanners

The section develops a simpler non-faulty spanner algorithm and combines it with VFT multiplicative spanners and hit-and-miss graph families to construct fault-tolerant spanners. It proves the construction’s stated stretch and edge bound using fault-aware clustering to bound distances after faults.

3.1 A New Algorithm for (Oϵ(kϵ), Oϵ(k))-Spanners (Without Faults)

  • After x Baswana–Sen steps, the clustering has expected size N · p^x and radius at most x, while the edge set has size Õ(x · N/p).Every edge from an unclustered vertex to a graph neighbor is represented within distance 2x − 1.Source: §3.1 · p. 17
  • The non-faulty construction has stretch α = O(⌈k^ε⌉/ε) and β = O(4^(1/ε) · k/ε).It is presented as simpler than [BP20], with a tradeoff in its dependence on ε.Source: §3.1 · pp. 16, 20

3.2 f-VFT (Oϵ(kϵ), Oϵ(k))-Spanner

  • The VFT construction starts with f-VFT Baswana–Sen, then applies non-faulty Baswana–Sen to virtual graphs from the hit-and-miss family using shared random coins.The shared coins ensure that each iteration produces the same center set, and the construction maps virtual-graph edges back to paths in the corresponding graph.Source: §3.2 · pp. 20–21
  • For any edge with an endpoint outside V*, H0 − F preserves distance at most 2⌈k^ε⌉ − 1 for every fault set of at most f vertices avoiding the endpoints.V* contains vertices that are f-VFT clustered in the Phase 0 clustering.Source: §3.2 · p. 20
  • Every (i,F)-clustered vertex v ∈ V \ F has dist_H−F(v,c_i,F(v)) ≤ r_(i+1)/3 for i from 0 to ℓ−1.The observation bounds the distance to a cluster center in the fault-free remainder of the spanner.Source: §3.2 · p. 22
  • If v is (i−1,F)-clustered but (i,F)-unclustered, then each (i−1,F)-clustered u within r′_i in G−F has dist_H−F(v,u) ≤ 2⌈k^ε⌉·r_i.For i = ℓ, the bound improves to 2⌈k^ε′⌉·r_i.Source: §3.2 · p. 23
  • For every fault set F of size at most f, distances satisfy dist_H−F(u,v) ≤ 6(ℓ+1)·⌈k^ε⌉·dist_G−F(u,v) + O(4^(1/ε)·k/ε).This is the global stretch bound of Claim 3.19.Source: §3.2 · p. 24
  • H is an f-VFT spanner with stretch α = O(k^ε/ε), β = O(4^(1/ε)·k/ε), and ˜O((c·f·log n)^(4^(2/ε))·n^(1+1/k)) edges.These are the bounds stated in Corollary 3.20; the section’s title specifies the stretch as (O_ε(k^ε), O_ε(k)).Source: §3.2 · p. 24

4 Path Systems Emerging in the FT-Greedy

This section analyzes the path system underlying the greedy VFT d→r-spanner, including how its invariants are preserved through updates. Using parks and a path-exchange lemma, it establishes pairwise conditions and bounds on paths added, size, progress, and boosts, supporting an application to the standard VFT greedy spanner.

4.1 Greedy VFT d →r spanner

  • The VFT greedy algorithm outputs a valid d→r-spanner by adding a length-d path whenever a fault set leaves its endpoints more than r apart.The analysis partitions added paths into L, counted through the path-system construction, and G, handled separately.Source: §4.1 · pp. 25–26

4.2 Parks and Fault Tolerance

  • A park with J-score above 1/2 contains a path through J that avoids any fault set of at most f vertices disjoint from J.For length-ℓ paths, the number containing J is at most (1/β)(2f)^(ℓ−|J|+1).Source: §4.2 · pp. 27–28

4.3 The Properties of P

  • Under s ≥ 2, f ≥ 1, and D ≥ 4s^2f, the path collections maintain invariants for fault tolerance, pairwise parks, bounded size, and progress per boost.Each vertex is boosted at each radius at most D + 4sf times; the invariants are proved by a delicate simultaneous induction because they depend on one another.Source: §4.3 · p. 29
  • O(sDn) paths enter L because each boost yields progress and each vertex can be boosted at each radius at most 2D times.There are at most r radii, with r := ⌈s/2⌉.Source: §4.3 · pp. 28–29
  • O(k^3 f^(1−1/k)n^(1+1/k)) edges suffice for the VFT 1→(2k−1) greedy multiplicative spanner.The analysis uses the path-system lemma to bound the L family and shows that the G family is empty for its chosen parameters.Source: §4.3 · p. 30

4.4 Proof of Lemma 4.12

  • The proof of Lemma 4.12 uses the score-concatenation claim attributed to [PPST25].The section describes a simultaneous induction over the maintained path-system properties as a main technical contribution.Source: §4.3 · p. 29, §4.4 · p. 31
  • Lemma 4.16 uses the park and J-full conditions to rule out a surviving u-to-v path of length at most s when dist_G-F(u,v) > s.The constructed paths have lengths ℓ and ℓ + 1, so their concatenation would have length 2ℓ + 1 ≤ s, contradicting the distance assumption.Source: §4.4 · p. 31
  • The update maintains bounded-size and progress invariants and proves weak and strong collective fault-tolerance bounds for the modified path block.The proof lower-bounds progress by subtracting paths damaged by faults, then uses the bounded boost count to re-establish the collective bounds.Source: §4.4 · pp. 32–33
  • Subclaim C gives p ≤ D + 4sf for the relevant update history; a configuration exceeding its I5 cap is ruled out.Source: §4.4 · pp. 32–33
  • The induction establishes that every update preserves all path-system invariants, including the pairwise park condition.The proof handles the modified path block and uses the path-exchange lemma to bound the score contributed by newly added paths.Source: §4.4 · p. 34

5 The VFT greedy

This section analyzes the VFT greedy spanner, modeling fault-aware connections among centers with virtual graphs, spread hypergraphs, and robust sunflowers. It bounds the paths added by the construction through a robust CLFT process and uses this analysis to prove Theorem 5.4.

5.1 The k →O(k) greedy spanner

  • The analysis bounds the exceptional set L by O(√k n^(1+1/k)) paths; for the remaining paths, the greedy √k→O(k) spanner adds only O~(n) paths.Source: §5.1 · pp. 35–36

5.2 The Faulty Setting

  • In the faulty setting, each path in G adds virtual edges between centers, with vertex lists recording which edges become faulty under a given fault set.The virtual process represents these edges by paths of length at most 3√(k/δ), allowing non-faulty virtual paths to model non-faulty connections in the graph.Source: §5.2 · p. 38
  • A virtual-process bound requires more than the existence of center connections: the analysis must capture the robust connections created together by each path in G.Without this structure, the virtual process may add graphs indefinitely when the underlying path collections are empty; the section identifies robust sunflowers as the additional property used in the subsequent analysis.Source: §5.2 · p. 39

5.3 Modeling the Center Connections Formed by G

  • Deleting a vertex set A from a q-spread hypergraph leaves a (q − |A|)-spread hypergraph whenever q > |A|.The section introduces spread hypergraphs to model center connections and invokes the spread lemma, citing and [Rao20].Source: §5.3 · pp. 39–40
  • For each path P_i, the center-connection families form a (1/2f, 1/2)-robust sunflower whose kernel is V(P′_i).The lemma assumes C′ ≥ max(2, 10C), with C from Lemma 5.11.Source: §5.3 · p. 40

5.4 The Robust CLFT Process

  • The process generalizes the color-list fault-tolerant greedy analysis of [PST24], recovering its size upper bound up to a factor w, with an essentially tight bound.[PST24] proved an O(fwn^(1+1/k)) size bound for list-colored graphs with lists of size at most w, tight assuming the girth conjecture.Source: §5.4 · pp. 41–42

5.5 Proof of Theorem 5.4

  • The virtual construction satisfies the robust CLFT process with w = ⌊k⌋ + 1 and t = 2⌈k⌉ − 1, so its addition bound yields Theorem 5.4’s desired bound.The construction adds B_i whenever P_i is considered; summing this bound with the bound on |L| completes the proof.Source: §5.5 · p. 44

6 Analysis of Vertex Fault Tolerant 2 →2k-spanners

The section analyzes the edge bound of the greedy VFT 2→2k-spanner, charging non-boosting steps to growth in auxiliary path collections kept small by park properties. For k = 2, it establishes the lower bound on spanner size by controlling low-degree additions directly and charging high-degree additions to increases in capped two-path counts.

6 Analysis of Vertex Fault Tolerant 2 →2k-spanners

  • The greedy VFT 2→2k algorithm outputs a spanner with O(k^3 f n^(1+1/k)) edges.This is the bound established by Theorem 6.1.Source: §6 · p. 44

6.1 The Analysis

  • The proof tracks three evolving path collections and charges non-boosting steps to substantial growth, which limits how many such steps can occur.The K collections are bounded using their park properties; a charge to K yields growth of at least Ω_k(f^(k−1)n^((k−1)/k)), and the same approach applies to the other K collection.Source: §6.1 · pp. 45–46
  • The R collection provides an additional charging target when neither K collection can be charged; its paths have length R and it also satisfies a park property.The analysis additionally bounds the number of R paths between distinct vertices by 24R · D^(R−1).Source: §6.1 · pp. 45–46
  • The K collections contain paths of lengths k + 1 and k, respectively, and their pairwise park properties bound their sizes.These properties support the charging argument by limiting the total growth available in the collections.Source: §6.1 · p. 46

6.2 A Tight Bound for k = 2

  • For k = 2, the VFT greedy (2 →4) algorithm produces a spanner with O(f^{1/2} n^{3/2}) edges, achieving the lower bound.Source: §6.2 · p. 50
  • The proof bounds low-degree path additions directly and charges high-degree additions to increases in a capped count of distinct 2-paths.For a path whose middle vertex has degree at least 4f^{1/2}n^{1/2}, the analysis shows the capped count increases across many neighbors.Source: §6.2 · pp. 50–51

A Sampling Lemma and Proof of Proposition 4.14

The proof samples centers from collections of paths and uses concentration and a union bound to obtain simultaneous path-collection properties. It then fixes one center set satisfying those properties across the graph.

A Sampling Lemma and Proof of Proposition 4.14

  • Each vertex has a path collection of size at least D^r, and sampling centers yields a subcollection of paths ending at centers with the stated properties.The sampling lemma handles p = 1 deterministically and otherwise applies Bernstein’s inequality and a union bound.Source: A Sampling Lemma and Proof of… · pp. 54–55
  • With probability at least 1 − 1/(100n), a union bound gives the simultaneous stated bounds on the sampled path subcollections for all nonempty J of size at most r.The count of such subsets is bounded using the at most 2D^r paths in P_v.Source: A Sampling Lemma and Proof of… · p. 55
  • For each path collection P_i in G, the proof uses critical edges to identify distinct indices ℓ and q, then bounds the fault-free distances along the noncritical path portions.Those portions have distances at most ℓ·s and (d − q)·s in H_i − F_i.Source: A Sampling Lemma and Proof of… · pp. 55–56
  • With probability at least 99/100, the sampled center set gives every relevant vertex a nonempty path subcollection satisfying the lemma’s second-bullet property.The proof also obtains |S| ≤ 2pn with probability at least 1/2, so one set S can satisfy both conditions.Source: A Sampling Lemma and Proof of… · p. 56

B Equivalence of d →r and (α, β)-spanners

Appendix B relates distance-threshold spanners to ratio-stretch spanners: a d→r spanner yields an (r/d,r)-spanner with essentially the same bounds. The conversion uses shifted distance thresholds and a union of spanners.

B Equivalence of d →r and (α, β)-spanners

  • A d→r spanner with at most s(n) edges yields an (r/d,r)-spanner with essentially the same bounds.The appendix states this implication directly.Source: B Equivalence of d →r and (α,… · p. 56
  • For each ℓ in [d−1], a d→r spanner gives a (d−ℓ)→(r−ℓ) spanner with at most s((ℓ+1)n) edges.The proof attaches a disjoint path of length ℓ to every vertex, applies the d→r guarantee, then restricts the resulting edges to the original graph.Source: B Equivalence of d →r and (α,… · p. 56
  • Taking the union of the shifted spanners gives an (r/d)-spanner, by routing along length-d segments and the remaining distance.The proof bounds the resulting distance by (r/d) times the original distance.Source: B Equivalence of d →r and (α,… · p. 56
Loading 2610.33934v1…