Graph Spanners: A Tutorial Review

Reyan Ahmed; Greg Bodwin; Faryad Darabi Sahneh; Keaton Hamm; Mohammad Javad Latifi Jebelli; Stephen Kobourov; Richard Spence

Source-linked AI summary

Graph Spanners: A Tutorial Review

Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, Richard Spence

arXiv:1909.03152v2Sep 7, 2019cs.DMcs.DSmath.CO

TL;DR

Graph-spanner research spans a rapidly growing literature of techniques and algorithmic bounds, with open questions remaining. This survey organizes that work and aims to provide a guiding reference.

Problem
The rapidly growing graph-spanner literature needs an accessible reference to its techniques, algorithmic bounds, and open problems.
Source: §15 · p. 59
Method
The survey introduces techniques for computing spanners, tabulates state-of-the-art bounds, and poses open problems.
Source: §15 · p. 59
Results
For greedy t-spanner size bounds, results for odd-integer stretch subsume other stretch values up to constant factors.
Source: §4.5 · p. 20
Takeaways & Limitations
The survey is intended as a guiding reference to the state of the field.
Source: §15 · p. 59
Whether sublinear spanners can match Thorup–Zwick emulator quality without an extra poly(1/ε) factor remains a major open question.
Source: §8.2 · p. 36

Abstract

from arXiv · show

This tutorial review provides a guiding reference to researchers who want to have an overview of the large body of literature about graph spanners. It reviews the current literature covering various research streams about graph spanners, such as different formulations, sparsity and lightness results, computational complexity, dynamic algorithms, and applications. As an additional contribution, we offer a list of open problems on graph spanners.

1. Introduction

This tutorial surveys graph-spanner formulations, results, methods, and applications, defining spanners by their distance distortion and the vertex pairs they preserve. It also discusses how the Girth Conjecture informs edge-count bounds and spanner optimality, alongside open questions about distortion functions and the conjecture’s validity beyond known values of k.

1. Introduction

The survey presents methods and open problems across spanner formulations, hardness, algorithms, dynamic and distributed settings, restricted graph classes, and applications, while de-emphasizing geometric spanners.Its method-based tutorial aims to help readers unfamiliar with the area understand common techniques.Source: §1 · p. 3, §1.1 · p. 4

1.1. Organization and Layout

The survey uses annotated references for quick lookup and organizes its coverage from preliminaries and classical results through algorithms, variants, dynamic and distributed settings, restricted graphs, and applications.Sections 4–9 emphasize methods and proofs; summary tables collect size and weight guarantees.Source: §1.1 · pp. 3–4

1.2. Notation and Preliminaries

The preliminaries establish graph, distance, weight, diameter, and degree notation, along with conventions for asymptotic bounds and approximation ratios.Graphs are assumed undirected and connected unless stated otherwise.Source: §1.2 · pp. 4–5

2. Graph Spanners

A spanner preserves selected graph distances within a distortion function: common forms include multiplicative t-stretch and linear αx+β distortion, with the required vertex pairs specified separately.The pair set can range from selected pairs to all vertex pairs.Source: §2 · pp. 5–6

2.1. Classical Results

A t-spanner preserves all-pairs distances within factor t, and it is enough to verify the condition on input edges rather than every vertex pair, as stated in Proposition 2.1 [136].The basic t-spanner problem seeks a subgraph satisfying dG′(u, v) ≤ t · dG(u, v) for every pair.Source: §2.1 · pp. 6–7

2.2. Sparsity and Lightness

For unweighted graphs, sparsity measures edge retention; for weighted graphs, lightness compares spanner weight with MST weight, and prior work gives polynomial-time sparse-spanner algorithms and approximation results [11, 124].Althöfer et al. also give a spanner whose weight is comparable to the MST weight; Kortsarz and Peleg [124] study sparse 2-spanners.Source: §2.2 · pp. 7–9

2.3. Relation to Minimum Spanning Trees

An MST can be an arbitrarily poor spanner: deleting one edge from an unweighted cycle yields an MST whose stretch is |V| − 1.Source: §2.3 · p. 9

2.4. Erd˝os’ Girth Conjecture

An unweighted graph of girth greater than t + 1 has no proper subgraph that is a t-spanner, so the extremal edge bound γ(n, t + 1) achieved by the construction cannot generally be reduced.Determining γ(n, k), even asymptotically, remains open.Source: §2.4 · pp. 9–10
The Girth Conjecture supports bounds on possible spanner edge counts and makes some constructions optimally sized only conditionally, unlike ’s unconditional size/distortion tradeoff.Baswana and Sen provide a linear-time algorithm for a construction with this conditional optimality.Source: §2.4 · p. 10
Assuming the Girth Conjecture, any (α, β)-spanner with O(n^{1+1/k}) edges must satisfy α + β ≥ 2k − 1; independently, Woodruff proves an Ω(k⁻¹n^{1+1/k}) lower bound for (1, 2k − 2)-spanners.Woodruff’s result holds for some n-node graph for every k ∈ N, regardless of whether the conjecture is true.Source: §2.4 · p. 10

2.5. Open Problems

Can distortion functions be discontinuous, for example by distorting small distances more than large ones or preserving close vertices while allowing more distortion for far ones?Source: §2.5 · p. 11
The Girth Conjecture is known for k = 1, 2, 3, or 5; whether it holds for other k remains open.Source: §2.5 · p. 11

3. NP-hardness and Hardness of Approximation

This section surveys hardness and approximation limits for basic multiplicative and additive spanners, including results for planar graphs and an open bounded-degree question.

3.1. NP-hardness of the basic t–spanner problem

Peleg and Sch¨affer show that deciding whether an unweighted graph has a t-spanner with at most m′ edges is NP-complete even for t=2; Cai proves minimum t-spanner is NP-hard for every fixed t≥2.For t≥3, Cai’s result holds even on bipartite graphs.Source: §3.1 · p. 11

3.2. Label Cover and hardness of approximation of the basic t–spanner problem

For k≥3, basic k-spanner cannot be approximated within a factor better than 2(log^(1−ε) n)/k, while k=2 admits an O(log n) approximation.Both maximization and minimization Label Cover are quasi-NP-hard to approximate within 2(log^(1−ε) n).Source: §3.2 · p. 12

3.3. NP–Hardness for Planar Graphs

On planar graphs, the basic problem is NP-complete for fixed t≥5 when unweighted and t≥3 when weighted; minimum t-spanner is also NP-hard for t∈{2, 3, 4}.The unweighted reduction is from planar 3-SAT.Source: §3.3 · p. 13

3.4. NP–Hardness of Additive Spanners

For every integer β≥1, deciding whether a graph has an additive +β-spanner with at most m′ edges is NP-hard.A parameterized algorithm for minimum additive (1, β)-spanner is polynomial-time only when removing a constant number of edges [122].Source: §3.4 · p. 13

4. The Greedy Algorithm for Multiplicative Spanners

The greedy multiplicative-spanner construction processes edges by nondecreasing weight, retaining an edge only when the current subgraph does not already approximate its distance. Its ordering supports girth and sparsity guarantees, but the greedy output can still be arbitrarily worse than an optimal spanner on particular graphs.

4.1. Kruskal’s Algorithm for Computing Minimum Spanning Trees

Kruskal’s algorithm sorts edges by weight and adds an edge only when its endpoints are disconnected in the current subgraph.The survey reviews it as the basis for the greedy spanner construction.Source: §4.1 · p. 14

4.2. The Greedy Algorithm for Multiplicative Spanners

Althöfer et al. sort edges by nondecreasing weight and add uv when the current path exceeds t·w_uv; unlike Kruskal, this need not preserve acyclicity.The resulting graph has no cycles on at most t+1 edges, and Kruskal’s algorithm is its t=∞ special case.Source: §4.2 · pp. 14–15
Any edge ordering yields a t-spanner, but the girth guarantee depends on the nondecreasing-weight ordering.The survey notes that this greedy framework relies on enforcing the spanner condition for edges in the input graph, unlike additive spanners, for which uses preprocessing before its greedy step.Source: §4.2 · p. 15

4.3. Existential Optimality of Greedy t–spanners

Filtser and Solomon [105] show that the only t-spanner of a greedy t-spanner is itself, yielding class-wide edge-count and weight bounds for classes closed under edge deletion.The theorem bounds the greedy output by m(t,n) edges and weight ℓ(t,n) for every graph in the class.Source: §4.3 · p. 17

4.4. Arbitrarily Bad Greedy t–spanners

For a family with 2<t<3 and suitably small ε, the greedy t-spanner can be Θ(n) worse than optimum in both edge count and weight.The example’s greedy output is the bipartite graph plus half the edges incident to an added vertex, whereas the optimum is a star.Source: §4.4 · p. 18

4.5. Sparsity and Lightness Guarantees for Greedy t–spanners

The greedy ordering is crucial for sparsity, and the survey gives edge-count and weight guarantees while noting that odd-integer stretch bounds subsume other stretch values up to constant factors.The cited theorem states a (2k−1)-spanner and a bound on its weight relative to the MST; later work improves greedy-spanner lightness to O_ε(n^(1/k)) without a k-dependent factor.Source: §4.5 · pp. 19–20

4.6. Summary of Greedy Algorithm Guarantees

Table 1 summarizes spanners given by the greedy algorithm and uses n=|V| and m=|E|.Source: Table 1 · p. 20

4.7. Open Questions

The survey leaves open whether a natural reverse-greedy algorithm exists and whether greedy methods extend to additive, mixed, subsetwise, or pairwise spanners.Source: §4.7 · p. 20

5. Clustering and Path Buying Methods

Clustering and path buying construct spanners in two stages: clustering handles local structure, while path buying adds inexpensive paths to enforce desired stretch. The framework admits flexible choices of clusters, edge rules, and path cost and value.

5. Clustering and Path Buying Methods

The framework first grows clusters and adds nearby edges, then buys cheap edges to achieve the required stretch.The clustering phase is typically cheaper in runtime; path buying is typically more expensive because it may examine all paths.Source: §5 · p. 20, §5.1 · pp. 21–22

5.1. General Approach

Clustering for spanners may use overlapping clusters and differs from standard partitioning methods such as k-means or spectral clustering.Clusters may additionally be required to cover all vertices or be pairwise disjoint, depending on the problem.Source: §5 · p. 21, §5.1 · p. 21
Path buying evaluates a path by its cost and value, with value measuring stretch improvement and cost typically measuring the weight of added edges.The proto-algorithm allows different initial clusters, edge-addition rules, cost and value definitions, and relations between those quantities.Source: §5.1 · pp. 21–22

5.2. Illustrating Example

The illustrated proto-path-buying algorithm returns a (1, 6, V × V)–spanner when its specified initialization, rules, and path parameters are used.The proof sketch uses an intermediate cluster on a shortest path; cluster diameter at most two and a counting argument yield the (1, 6) stretch condition.Source: §5.2 · pp. 23–24

5.3. Theme and Variations

Cygan et al. give a polynomial-time clustering and path-buying algorithm for pairwise, subsetwise, and sourcewise spanners, using a deterministic variant of Baswana et al.’s clustering.Their derandomization is described as orthogonal to changing from all-pairs to pairwise spanners.Source: §5.3 · p. 24

Clustering Phase

The clustering phase selects fixed-size clusters around centers, adds specified local edges, and leaves some vertices unclustered. Its properties bound cluster count and diameter and support an O(nd) edge bound.

Clustering Phase

The cluster-selection procedure repeatedly chooses d unmarked neighbors of a vertex as a cluster, marks them, and stops when no vertex has d unmarked neighbors.The center is not included in the cluster.Source: Clustering Phase · p. 24
The clustering rules add intracluster edges and center-to-cluster edges, while adding every incident edge of each vertex outside a cluster.An absent edge in E′ must join vertices in different clusters, and neither endpoint can be unclustered.Source: Clustering Phase · pp. 24–25
Each cluster has exactly d vertices, there are at most n/d clusters, and every cluster has diameter at most 2 in G′.Vertices in the same cluster have a common neighbor in G′.Source: Clustering Phase · pp. 24–25
The two edge-addition rules together contribute O(nd) edges: Rule 1 adds at most O(nd), and Rule 2 does likewise by bounding each vertex’s unmarked neighbors by d.The proof uses a union bound over the n vertices for Rule 2.Source: Clustering Phase · p. 25

Path Buying Phase

Path-buying variants combine cluster structure with choices of path cost, value, and α to obtain different spanner guarantees. The section also surveys further constructions and poses an open question about using conventional graph clustering.

Path Buying Phase

With the specified cost and value and α = 2, clustering plus path buying yields an additive subsetwise spanner with additive stretch 2.For S ⊆ V, choosing d = √|S| balances O(nd) clustering edges against O(|S|n/d) path-buying edges to minimize the final size.Source: Path Buying Phase · p. 25
Combining the proto-path-buying output E1 with an O(n)-size (2 log n, 0, V × V)–spanner E2 yields a (1 + ε, 4, P)–spanner.The variant uses path buying as preprocessing in a larger construction.Source: Path Buying Phase · pp. 25–26

5.4. Further Reading

Baswana and Sen obtain a (2k − 1)–spanner with O(n^(1+1/k)) edges in expected O(kn) time, with optimal edge count up to a constant assuming the Girth Conjecture and optimal time.Baswana et al. report an additive 6–spanner of size O(n^(4/3)) and a linear-time (k, k − 1)–spanner construction of size O(n^(1+1/k)).Source: Path Buying Phase · p. 26, §5.4 · p. 27
Pettie presents a modular connection-scheme approach that generates most existing results and gives linear-size spanners with stretch (5 + ε, polylog(n)) and (1, eO(n^(9/16))).The latter bound was later improved to (1, O(n^(3/7+ε))) in; Elkin and Peleg also give efficiently constructible (1+ε, β)–spanners of size O(n^(1+λ)) for constants λ > 0 and β = β(ε, λ).Source: Path Buying Phase · pp. 26–27, §5.4 · p. 27

5.5. Open Problems

The open problem asks whether traditional disjoint, covering graph clusters from methods such as spectral or hierarchical clustering can produce a good spanner.Source: §5.5 · p. 27

6. Probabilistic Methods

The survey describes randomized constructions that provide spanner guarantees with high probability, including a construction improved by Elkin and Neiman. It also identifies open questions about improving the size guarantee and sampling edges to obtain spanners.

6. Probabilistic Methods

Miller et al. give the first randomized algorithm producing a spanner with high probability, with a multiplicative O(k) stretch and expected size O(n^(1+1/k) log k) in expected O(m) time.Source: §6 · p. 28
Elkin and Neiman construct a (2k − 1)–spanner with O(n^(1+1/k) ε^−1) edges with probability 1 − ε, improving on Miller et al..Their analysis covers runtime and edge count in both PRAM and CONGEST models.Source: §6 · p. 28

6.1. Probabilistic

Elkin and Neiman’s analysis uses exponential random variables and their memoryless property; when event X holds, Algorithm 6 has stretch at most 2k − 1.The proof bounds the probability that any vertex’s sampled radius reaches k, then uses a size bound for the resulting edge set.Source: §6.1 · pp. 28–29

6.2. Open Problems

The open problems ask whether optimizing Elkin and Neiman’s probability density function can improve spanner size, and whether edge distributions can yield a spanner with high probability by sampling.Source: §6.2 · p. 29

7. Subsetwise, Sourcewise, and Pairwise Spanners

Pairwise distance preservers preserve exact distances for specified vertex pairs, and their edge-size bounds depend on the graph and the number of pairs. The section surveys upper bounds, proof ideas, related work, and open questions for pairwise and terminal spanners.

7.1. Pairwise Distance Preservers

A distance preserver keeps distances exact for specified pairs, and the survey asks how its edge count depends on n and the pair set P.Some spanner constructions use distance preservers as a subroutine.Source: §7.1 · p. 30
For undirected weighted or unweighted graphs, a distance preserver exists with O(n + n^1/2|P|) edges; for directed or undirected graphs, one exists with O(n + n^2/3|P|) edges.The latter bound applies to weighted and unweighted graphs as well.Source: §7.1 · p. 31

7.2. Sketch of Proof of Theorem 7.2

Consistent tiebreaking makes shortest-path subpaths agree, supporting the proof strategy that bounds preserver size through branching triples.The sketch partitions P into subsets of size O(n^1/3) and applies the resulting sparse-preserver argument to each subset.Source: §7.2 · p. 31

7.3. Further Reading

Bodwin and Williams give a pairwise-preserver upper bound, while Abboud and Bodwin show that pairwise-preserver lower bounds imply pairwise-spanner lower bounds.The survey also notes a connection to reachability preservers, which preserve reachability rather than distances.Source: §7.3 · p. 32

7.4. Multiplicative Pairwise Spanners

A terminal graph spanner is a sourcewise spanner preserving pairs in K × V; a construction in has stretch 4t − 1 and O(n + √n|K|^(1+1/t)) edges.The construction combines a metric spanner, a distance preserver, and a shortest-path tree rooted at K.Source: §7.4 · p. 32

7.5. Open Problems

For |P| = n^(1+c), multiplicative pairwise spanners are nontrivial only in a restricted parameter range, and the survey asks how many pairs admit an O(n)-edge additive spanner.The open question asks for the largest p(n) for which any p node pairs in an undirected unweighted n-node graph can be spanned with +c error; +0 error is known for O(n^1/2) pairs.Source: §7.4 · p. 32, §7.5 · p. 33

8. Extremal Bounds for Additive, Mixed, and Sublinear Spanners

The survey organizes extremal spanner results around tradeoffs between sparsity and distortion. It reviews additive bounds and barriers, mixed and sublinear hierarchies, weighted-graph considerations, and open problems.

8.1. Purely Additive Spanners

For all graphs, additive +2-spanners have O(n^(3/2)) edges, improving the eO(n^(3/2)) bound implicit in Aingworth et al., while additive +6-spanners have O(n^(4/3)) edges.Source: §8.1 · pp. 33–34
For 0 < ε < 1/3, an O(n)-edge additive spanner requires +Ω(n^1/13) error, and O(n^(1+ε))-edge spanners cannot achieve subpolynomial additive error.Huang and Pettie improve the cited lower bound from +Ω(n^1/22) to +Ω(n^1/13).Source: §8.1 · p. 34

8.2. Mixed and Sublinear Spanners

The survey frames mixed spanners as combining (1 + ε) multiplicative stretch with +β additive stretch, while sublinear spanners use additive error that depends sublinearly on distance.It describes the two paradigms as responses to limits on near-linear-size purely additive spanners.Source: §8.2 · p. 35
Mixed-spanner bounds form a hierarchy with β = O(1/ε)^(k−1); matching sublinear spanner quality from Thorup–Zwick emulators without an extra poly(1/ε) factor remains open.The emulator-to-spanner conversion described in the survey adds that factor.Source: §8.2 · pp. 35–36
Thorup–Zwick-type sublinear error f(d) = O(d^(1−1/k)) is singled out because other sublinear error functions can require Ω(n^4/3−o(1)) edges even when constant additive error is achievable at that size.The survey also reports lower bounds showing the Thorup–Zwick emulator hierarchy is essentially optimal.Source: §8.2 · p. 36

8.3. Additive and Mixed Spanners of Weighted Graphs

For weighted inputs, a fixed additive error such as +2 can be trivialized by scaling edge weights, motivating error proportional to maximum edge weight; one construction scales it to the maximum weight on each true shortest path.The survey cites purely additive constructions in [6] and mixed constructions in [88].Source: §8.3 · p. 36

8.4. Open Problems

Open problems include whether +4 additive spanners can use O(n^4/3) edges, whether Thorup–Zwick emulators can become comparable spanners, and how much error O(n)-edge additive spanners require.The cited best +4 bound is O(n^7/5), while the cited Oε(n)-edge construction has +O(n^3/7+ε) error and the lower bound is +Ω(n^1/13).Source: §8.4 · p. 37

9. Linear Programming Formulations

This section surveys LP and ILP formulations for spanner problems, including relaxations, integrality gaps, and exact formulations. It describes a polynomial-size flow-based ILP for pairwise spanners that supports arbitrary distortion and directed inputs.

9.1. Quick Introduction to Linear Programming and Duality

LP relaxations remove integrality requirements to approximate hard ILPs, while integrality gap measures the maximum ratio between the ILP and relaxed LP solutions.Lift-and-project methods add variables in higher dimensions before projecting back, and the survey notes Sherali–Adams and Lasserre hierarchies.Source: §9.1 · pp. 38–39

9.2. An LP Relaxation of the Multiplicative Spanner Problem

For directed t-spanners, Dinitz and Krauthgamer formulate an LP using edge-selection variables and flows over paths no longer than t·dG(u,v).The survey describes using a dual separation approach to handle exponentially many path constraints.Source: §9.2 · pp. 39–40
The directed t-spanner primal LP has a polynomial-time (1 + ϵ)-approximation algorithm, while the survey also reports an integrality-gap result for that LP.The supplied passage for the gap theorem does not provide its bound.Source: §9.2 · p. 40

9.3. ILPs for Pairwise Spanners

The pairwise multiplicative-spanner ILP selects feasible paths and their edges, enforcing edge inclusion for selected paths and at least one t-spanner path per demand pair.Column generation solves a restricted master problem optimally, and the ILP shows the greedy algorithm is optimal in many cases.Source: §9.3 · p. 41
Ahmed et al. [8] give a polynomial-size flow-based ILP for pairwise spanners with arbitrary distortion, including directed inputs, and report experiments supporting feasibility.The survey presents this as an affirmative resolution to the open question of a practical polynomial-size pairwise-spanner ILP.Source: §9.3 · p. 41
For pairwise formulations, the general distortion function allows broad flexibility, while the noted variable-count reductions apply specifically to multiplicative spanners.The survey reports 2|E||P| binary variables for one pairwise ILP and notes that the full-spanner variable count grows with |E||V|(|V| − 1).Source: §9.3 · p. 42
The survey covers additional LP-based results, including a stronger Lasserre integrality-gap result [79] and a Sherali–Adams approximation for lowest-degree 2-spanners.It also reports a hardness-of-approximation bound for lowest-degree k-spanners for k ≥ 3, unless NP ⊂ BPTIME(2^polylog(n)).Source: §9.3 · p. 42

10. Distributed and Streaming Algorithms

The survey reviews algorithms for constructing spanners in distributed, streaming, and dynamic settings. It highlights tradeoffs among sparsity, distortion, computation rounds, and stream space.

Distributed algorithms

Distributed algorithms construct spanners to sparsify networks while limiting communication latency, with work spanning LOCAL and CONGEST models.The survey notes that early spanner applications included synchronizers for converting between asynchronous and synchronous distributed computation.Source: §10 · p. 44
Distributed results include a fast O(2^(log* n) log n)-spanner of size O(n), additive 2-spanner construction in O(n^1/2 log n + diam(G)) CONGEST rounds, and near-linear-size Fibonacci spanners.Pettie also gives lower bounds on tradeoffs among time, sparseness, and distortion.Source: §10 · p. 44
Deterministic distributed constructions include O(k n^(1+1/k))-edge O(k)-spanners and (2k − 1, 0)-spanners in k rounds, with a sub-polynomial-round lower bound for comparable-size spanners.The survey also notes distributed constructions with controlled lightness [87].Source: §10 · p. 45

Streaming and dynamic algorithms

Elkin gives near-optimal size/stretch streaming spanners with O(1) expected processing time per edge, and a close variant supports fully dynamic maintenance with similar update time.The survey also describes a dynamic-stream construction using O(n^(1+1/k)) bits for a multiplicative 2k-spanner.Source: §10 · p. 45

11. Special Types of Spanners

This section surveys spanners and related distance-approximation objects, including emulators, distance oracles, and spanners that preserve graph diameter or vertex eccentricities. It contrasts their guarantees and uses, including settings where emulator bounds are known but corresponding spanner questions remain open.

11.1. Emulators

Emulators achieve O(n^4/3) edges with 4-additive error, while a matching-size spanner with 4-additive error remains open; the known spanner bound is 6-additive.The emulator guarantee is described as optimal in the edge bound and additive error considered separately.Source: §11.1 · p. 46
For fixed k, emulator constructions have 1 + 1/(2k−1) edges and error d + O(d^(1−1/k)); these bounds are essentially optimal.Emulators also support approximate APSP approaches that build sparse emulator sequences before running shortest-path algorithms [81].Source: §11.1 · p. 46
For planar graphs with terminal set T, an emulator has eO(min{|T|^2, n|T|}) edges and exactly preserves terminal-pair distances; it supports distance queries in eO(n) time when |T| = eO(n^1/3).The time guarantee is for the stated terminal-size range.Source: §11.1 · p. 46

11.2. Approximate Distance Oracles

Approximate distance oracles answer distance queries without returning a subgraph, and Thorup–Zwick’s randomized oracle has stretch 2k−1, O(kmn^(1/k)) runtime, and O(kn^(1+1/k)) space.Spanners are more restrictive because they must be subgraphs.Source: §11.2 · p. 47
Source-restricted and deterministic oracle variants trade runtime and scope differently: sourcewise queries are useful when |S| ≪ n, while derandomization adds a logarithmic runtime factor.The sourcewise variant uses O(km|S|^(1/k)) runtime and O(kn|S|^(1/k)) space; the deterministic variant retains the randomized algorithm’s space bound.Source: §11.2 · p. 47

11.3. Diameter and Eccentricity Spanners

Directed diameter and eccentricity spanners have distinct guarantees: an unweighted directed graph admits a deterministic 1.5-diameter spanner with O(n^(3/2)√log n) edges, while a weighted directed graph admits a Las Vegas 2-eccentricity spanner with O(n log^2 n) edges.The diameter construction runs in eO(m√n) time; the eccentricity construction runs in eO(m) expected time.Source: §11.3 · pp. 48–49

Hardness

The surveyed variants have different approximation guarantees and complexity boundaries, from conditional hardness results to tractable constructions on restricted graph classes. The section also summarizes specialized spanners for terminal sets, spanning trees, low degree, and doubling metrics.

Hardness

Unless SETH fails, no O(n^(3/2−δ))-time algorithm approximates sparse weighted-graph diameter below ratio 5/3, or sparse unweighted undirected-graph eccentricities below ratio 9/5.Here δ > 0.Source: Hardness · p. 49

11.4. Ramsey Spanning Trees

A polynomial-time construction finds a source set of size at least n^(1−1/k) and a spanning tree that is an (O(k log log n), 0, S × V)-spanner.This is presented as a graph generalization of the metric Ramsey problem.Source: §11.4 · p. 49

11.5. Slack Spanners

An ε-slack spanner preserves, for each vertex, distances to its furthest (1−ε)n vertices within O(log(1/ε)) distortion using O(n) edges.Gracefully degrading existing spanners also have O(1) average stretch and O(n) size.Source: §11.5 · p. 49

11.6. Spanners in Sparse Graphs

Computing a t-spanner is fixed-parameter tractable in t and treewidth k for planar graphs, and also on graphs excluding a fixed apex graph as a minor.An apex graph is planar after one vertex is removed.Source: §11.6 · p. 50

11.7. Steiner t-Spanners

For Steiner t-spanners, the distances to preserve are between terminals; minimum Steiner t-spanner is not approximable within (1−ε) log |S| unless NP ⊆ DTIME(n^(log log n)).Here S denotes the Steiner vertices, as stated in the passage.Source: §11.7 · p. 50

11.8. Tree t–spanners

Tree 1-spanners can be found in O(m log β(m,n)) time and tree 2-spanners in O(m+n) time, but deciding existence for t ≥ 4 is NP-hard.Minimum max-stretch spanning trees also have an O(log n)-approximation, with hardness against ratios below 5/4.Source: §11.8 · pp. 50–51

11.9. Lowest-degree k-Spanners

For lowest-degree spanners, the k=2 approximation is approximately Õ(Δ^0.172), while for k ≥ 3 the approximation is Õ(Δ^(1−1/k)^2); both settings also have stated hardness bounds.For k=2, no ratio better than (ln n)/5 is possible under the stated complexity assumption [123]; for k ≥ 3, the hardness is Δ^Ω(1/k) unless NP ⊆ BPTIME(2^polylog(n)).Source: §11.9 · p. 51

11.10. Spanners for Doubling Metrics

For constant doubling dimension, geometric-spanner guarantees extend to the metric setting, including constant maximum degree, O(log n) hop-diameter, and O(log n) lightness.For doubling dimension d, a greedy (1+ε)-spanner has weight ε^−O(d)W(MST(G)).Source: §11.10 · p. 52

12. Spanners For Changing Graphs

This section reviews spanners designed to remain useful under faults, edge changes, or other alterations to the input graph. The surveyed results include fault-tolerant and resilient constructions, dynamic update guarantees, and open questions about their scope.

12.1. Fault Tolerant Spanners

Fault-tolerant spanners preserve stretch after up to f edge or vertex failures, with constructions spanning randomized bounds and later improvements in size.The cited results include (2k−1)-spanners with high probability and improved fault-size dependence via a transformation from an ordinary spanner to a fault-tolerant one.Source: §12.1 · p. 53
For fault-tolerant BFS structures, tight edge or vertex fault bounds are given for f=1 and f=2, but the general-f upper and lower bounds remain separated.The survey identifies closing this gap as an open question.Source: §12.1 · pp. 54–55

12.2. Resilient Spanners

Resilience controls how much an edge’s fragility can exceed the larger of σ and its original fragility; dense graphs may admit no 2-resilient spanner other than the graph itself [16].A polynomial-time construction gives a σ-resilient (2k−1)-spanner for σ ≥ 2k−1 and k ≥ 2, with O(Wn^(3/2)) edges and O(mn+n^2 log n) runtime.Source: §12.2 · p. 55

12.3. Dynamic Algorithms

Dynamic spanner algorithms maintain distortion as input edges are inserted or deleted, and the surveyed dynamic results concern multiplicative error.Known guarantees include amortized update times and later worst-case update-time constructions.Source: §12.3 · p. 56
A key open question is whether dynamic spanners can achieve non-oblivious update guarantees, where the adversary may choose updates based on the algorithm’s random bits.This matters when dynamic spanners are subroutines and later graph updates can depend on the spanner’s current state.Source: §12.3 · p. 56

13. Spanners for Special Classes of Graphs

The survey highlights selected results for restricted graph classes and directed graphs, emphasizing results rather than techniques. Geometric spanners receive limited coverage because an external book treats them extensively.

13. Spanners for Special Classes of Graphs

For special graph classes, the survey highlights results rather than techniques except where appropriate.It does not cover geometric spanners in depth because the cited book provides an extensive treatment.Source: §13 · p. 57, §13.1 · p. 57

13.2. Directed Graphs

Directed spanners require maintaining connectivity, and surveyed approaches include flow-based and anti-spanner formulations, approximation algorithms, and roundtrip variants.Dinitz et al. provide an Õ(n^1/3)-approximation for directed 4-spanner.Source: §13.2 · p. 57

14. Applications of Graph Spanners

The survey describes graph spanners as tools across distributed computing, routing, biology, and theoretical applications. It closes by aiming to organize the field’s techniques and algorithmic bounds while identifying open problems.

14. Applications of Graph Spanners

Sparse spanners trade minor propagation latency for reduced communication and processing demands in distributed systems.Applications include communication networks, synchronizers, broadcasting, queuing protocols, sensor networks, load balancing, and robotics.Source: §14 · p. 58
Routing algorithms use spanners as one step, but must also balance path efficiency against information stored at nodes and in packet headers.The discussion extends message routing to examples such as cars in road networks.Source: §14 · p. 58
Spanners help represent biological history by retaining important connections in weighted graphs built from pairwise similarity matrices.The survey cites genetic-distance measurement and protein-interaction visualization.Source: §14 · p. 58
Graph spanners can serve as preprocessing for algorithms whose runtime depends on edge count, including PTASs for traveling salesperson.Improved spanners on special graph classes can also improve these PTASs; examples include planar, bounded-genus, unit-disk, and bounded-path-width graphs.Source: §14 · p. 59
Spanners can capture network backbones and properties beyond distances, including the network spectrum, and have been used to construct spectral sparsifiers.Other applications include geometric distances, sublinear-time property testing, facility location, cycle covers, and distance-labeling schemes [68].Source: §14 · p. 59

15. Conclusion

The survey aims to organize spanner techniques and state-of-the-art algorithmic bounds, while posing open problems for experts and non-experts.It hopes to serve as a guiding reference as the literature continues to grow.Source: §15 · p. 59

Appendix A. Tables of Spanner Guarantees

The appendix presents tables of guarantees for several graph-spanner formulations. Their captions identify the formulation-specific scope and clarify selected parameters and notation.

Appendix A. Tables of Spanner Guarantees

Table A.2 collects guarantees for multiplicative spanners, with weight bounds scaled by W(MST(G)).The caption defines n = |V|, m = |E|, and α(n) as the inverse Ackermann function; ** marks complexities not given in the paper.Source: Table A.2 · p. 73
Table A.3 collects additive-spanner guarantees and uses D for the graph diameter.The caption defines n = |V| and m = |E| and marks complexities not given in the paper with **.Source: Table A.3 · p. 73
Table A.4 collects guarantees for (α, β)-spanners and notes a condition required in [84].The caption states the condition as ρ > 1 2k.Source: Table A.4 · p. 74
Table A.5 collects guarantees for pairwise and subsetwise spanners.Its caption notes that [118] gives a constant-approximation algorithm for multiplicative subsetwise spanners on planar graphs.Source: Table A.5 · p. 74
Table A.6 collects guarantees for fault-tolerant spanners, distinguishing edge-fault from vertex-fault tolerance.The caption defines f as the number of allowed faults and marks high-probability constructions with an asterisk beside the citation.Source: Table A.6 · p. 75