Introduction
The Steiner tree problem asks for a minimum-weight connected subgraph connecting a specified set of terminals in an undirected weighted graph. This NP-hard problem is a fundamental abstraction of network design where a set of target endpoints must be connected with minimum cost using intermediate nodes as optional relays. Consequently, it has motivated decades of work on polynomial-time approximation algorithms in the static setting. A classical algorithm by Kou, Markowsky, and Berman achieved a 2-approximation by constructing a minimum spanning tree on the metric closure of the terminals (metric MST ) [KMB81], and Mehlhorn showed how to compute such a tree in O ( m + n log n ) O(m+n \log n) O ( m + n log n ) time [Meh88]. Zelikovsky later improved the approximation factor to 11 / 6 11/6 11/6 [Zel93], and subsequent work reduced it further to 1.746 1.746 1.746 [BR94], 5 / 3 + ε 5/3+\varepsilon 5/3 + ε [PS00], 1.644 1.644 1.644 [KZ97], and 1.598 1.598 1.598 [HP99]. This line of work continued with the 1.55-approximation of Robins and Zelikovsky [RZ05], culminating in the best-known ( ln 4 + ε ) (\ln4+\varepsilon) ( ln 4 + ε ) -approximation of Byrka et al. [BGRS13] for any fixed ε > 0 \varepsilon>0 ε > 0 . Our focus is on the dynamic version of this problem, where the goal is to maintain an approximate Steiner tree under edge updates, while the vertex and terminal sets remain fixed.
Steiner tree naturally generalizes minimum spanning tree : when every vertex is a terminal, the two problems coincide. Dynamic MST is one of the most fundamental problems in dynamic graph algorithms, serving as a natural abstraction of evolving networks and the primary motivation behind foundational dynamic tree data structures and techniques. Over forty years ago, Frederickson introduced topology trees to achieve an O ( m ) O(\sqrt{m}) O ( m ) worst-case update bound for maintaining an MST in an n n n -vertex m m m -edge graph under edge updates [Fre85]. For the incremental setting, Sleator and Tarjan’s link-cut trees [ST81] maintained an MST in O ( log n ) O(\log n) O ( log n ) time. To overcome graph density, Eppstein, Galil, Italiano, and Nissenzweig developed sparsification trees to obtain the first bound sublinear in n n n [EGIN92, EGIN97]. Later, Holm, de Lichtenberg, and Thorup combined Euler tour trees with hierarchical edge levels to achieve O ( log 4 n ) O(\log^4 n) O ( log 4 n ) amortized update time [HdLT01]. Despite their close relationship and more than four decades of progress on dynamic MST, comparable sublinear update time bounds have not previously been established for constant-factor Steiner tree approximation under edge updates in general weighted graphs. This gap motivates the following question:
Is there a fully dynamic (or even incremental) algorithm that maintains an O ( 1 ) O(1) O ( 1 ) -approximate Steiner tree in general weighted graphs with sublinear-in-n n n update and cost-query time?
The above question has remained open across almost all regimes, including sparse unweighted graphs. In fact, the only known dynamic algorithm under edge updates, which improves upon recomputing from scratch, is an application of the additive spanner of Bergamaschi, Henzinger, Probst Gutenberg, Vassilevska Williams, and Wein [BHPG$^{+}$21], which achieves O ( n 1.529 + k 2 n 1 + o ( 1 ) ) O(n^{1.529}+k^2n^{1+o(1)}) O ( n 1.529 + k 2 n 1 + o ( 1 ) ) update time, where k k k is the number of terminals. However, their algorithm applies solely to unweighted graphs, and requires both a sublinear number of terminals and a dense graph to beat static recomputation. A separate line of work, dating back to Imase and Waxman [IW91] and studied extensively in online recourse models [GGK13, GK14] and dynamic settings [LOP$^{+}$15], considers terminal arrivals and departures in a fixed graph. Leaving the underlying graph metric invariant, their results cannot extend to edge updates. Finally, while dynamic distance oracles and vertex sparsifiers maintain pairwise distances efficiently, they would require at least Ω ( k ) \Omega(k) Ω ( k ) work to recalculate terminal distances. The fundamental obstacle is that a single edge update can simultaneously disrupt many shortest paths shared across multiple terminal pairs, and identifying which routes are invalidated and finding replacement paths in o ( n ) o(n) o ( n ) time has remained unresolved.
Our Contribution. We give a strong affirmative answer to the question above.
Theorem 1.1. Let G G G be a connected n n n -vertex fully dynamic undirected graph with m 0 m_0 m 0 edges initially, a terminal set R R R , and polynomially bounded edge weights over all updates. For every fixed 0 < ζ < 1 / 2 0 < \zeta< 1/2 0 < ζ < 1/2 , there is a deterministic fully dynamic algorithm that maintains an O ζ ( 1 ) O_{\zeta}(1) O ζ ( 1 ) -approximate Steiner tree for R R R in G G G with O ~ ( n 1 / 2 + ζ ) \widetilde{O}(n^{1/2+\zeta}) O ( n 1/2 + ζ ) amortized update time and O ( ( m 0 + n ) n ζ ) O((m_0+n)n^{\zeta}) O (( m 0 + n ) n ζ ) initialization time. After every update, cost queries take O ( 1 ) O(1) O ( 1 ) time, and reporting the Steiner tree takes O ~ ( n 1 + ζ ) \widetilde{O}(n^{1+\zeta}) O ( n 1 + ζ ) time.
Ours is the first fully dynamic algorithm that maintains a constant-factor approximate Steiner tree in sublinear-in-n n n update time across all graph densities and with no dependence on the terminal-set size. Notably, we also achieve robustness against an adaptive adversary and near-linear O ~ ( n 1 + ζ ) \widetilde{O}(n^{1+\zeta}) O ( n 1 + ζ ) reporting time. See also Theorem 4.13 for a detailed version of this result.
In terms of techniques, we compute a terminal-metric MST on a sparse dynamic spanner, expanding this MST into a single tree so that any edge deletion breaks at most one tree edge. As an update arrives, a dynamic program over a fixed top-tree hierarchy [3 ] decides in O ( log n ) O(\log n) O ( log n ) time which parts of this tree to keep, leaving a small number of components to reconnect. We estimate the reconnection cost by running Mehlhorn’s algorithm [Meh88] on a dynamic vertex sparsifier. When an explicit tree is requested, we instead run Mehlhorn’s algorithm on the current spanner to reconnect these components. Our final bounds are obtained using the deterministic dynamic spanner of Chuzhoy and Parter [CP25] and the deterministic dynamic vertex sparsifier of Haeupler, Long, and Saranurak [HLS24]; any improvement to their results would carry over directly to ours.
When updates consist only of edge insertions, we obtain a simpler randomized algorithm using elementary combinatorial tools that achieves a better approximation constant.
Theorem 1.2. Let G G G be a connected n n n -vertex incremental undirected graph with m 0 m_0 m 0 edges initially, a terminal set R R R , and polynomially bounded edge weights over all updates. For every fixed 0 < ζ < 1 / 3 0 < \zeta< 1/3 0 < ζ < 1/3 , there is a randomized insertion-only algorithm that maintains an O ( 1 / ζ 2 ) O(1/\zeta^2) O ( 1/ ζ 2 ) -approximate Steiner tree for R R R in G G G with O ~ ( n 2 / 3 + ζ ) \widetilde{O}(n^{2/3+\zeta}) O ( n 2/3 + ζ ) expected amortized update time and O ~ ( m 0 + n 1 + ζ ) \widetilde{O}(m_0+n^{1+\zeta}) O ( m 0 + n 1 + ζ ) expected initialization time. After every insertion, the approximation guarantee holds deterministically, cost queries take O ( 1 ) O(1) O ( 1 ) time, and reporting the Steiner tree takes O ~ ( n 4 / 3 + ζ ) \widetilde{O}(n^{4/3+\zeta}) O ( n 4/3 + ζ ) time.
In particular, we can get a ( 162 + ε ) (162+\varepsilon) ( 162 + ε ) -approximation in O ~ ( n 14 / 15 ) \widetilde{O}(n^{14/15}) O ( n 14/15 ) update time; see Theorem A.7 for the full parameterized statement. Our incremental algorithm combines a dynamic spanner [BKS12] and a static distance oracle [TZ05] to maintain shortest paths among the endpoints of newly inserted edges. Extending these paths to each endpoint’s nearest terminal yields terminal-to-terminal shortcuts whose weights only decrease over time, allowing us to maintain the resulting terminal MST dynamically via link-cut trees [ST81].
Technical Overview
In this work, we develop a dynamic framework that maintains an approximate terminal-metric spanning structure under edge updates, simultaneously achieving a constant approximation factor and sublinear-in-n n n update time. From this structure we can read off the Steiner tree cost and report its edges efficiently. Our framework is presented in three steps. We begin by examining basic baselines obtained by combining known dynamic data structures and basic Steiner tree algorithms (§ 1.1.1 ), showing why off-the-shelf combinations either incur prohibitive query time or sacrifice constant approximation. We then introduce our periodic rebuilding framework in the simpler insertion-only setting (§ 1.2 ), and finally build on these ideas to obtain our deterministic fully dynamic algorithm (§ 1.2.1 ).
Baselines for Steiner cost estimation
Before describing our framework, we examine how existing dynamic primitives can be used to estimate the Steiner optimum. Table 1 summarizes the following direct reductions and compares them with our fully dynamic result.
A classical static 2-approximation offers a natural starting point. For an undirected weighted graph G G G and terminal set R R R of size k = ∣ R ∣ k = |R| k = ∣ R ∣ , consider the complete graph on the terminals denoted by K G ( R ) K_G(R) K G ( R ) , with each edge weighted by its shortest-path distance d G ( u , v ) d_G(u,v) d G ( u , v ) in the underlying graph. An MST of this terminal metric closure K G ( R ) K_G(R) K G ( R ) expands into a Steiner tree of at most twice the optimum weight OPT G ( R ) \operatorname{OPT}_G(R) OPT G ( R ) [KMB81], cf. Lemma 2.6 . To avoid constructing the Θ ( k 2 ) \Theta(k^2) Θ ( k 2 ) -edge clique K G ( R ) K_G(R) K G ( R ) explicitly, Mehlhorn [Meh88] runs a single multi-source Dijkstra computation from R R R to partition V V V into Voronoi regions around each vertex’s nearest terminal a ( x ) ∈ R a(x) \in R a ( x ) ∈ R at distance δ ( x ) = d G ( a ( x ) , x ) \delta(x) = d_G(a(x),x) δ ( x ) = d G ( a ( x ) , x ) , contracts each region into its terminal root so that every cross-region edge x y xy x y induces a candidate edge between a ( x ) a(x) a ( x ) and a ( y ) a(y) a ( y ) of weight δ ( x ) + w ( x y ) + δ ( y ) \delta(x) + w(xy) + \delta(y) δ ( x ) + w ( x y ) + δ ( y ) , and computes an MST of this sparse candidate graph in O ( m + n log n ) O(m + n \log n) O ( m + n log n ) time, cf. Theorem 2.8 . Maintaining this construction under edge updates to G t G_t G t , however, presents significant algorithmic challenges. First, a single insertion or deletion can alter shortest-path distances across Θ ( k 2 ) \Theta(k^2) Θ ( k 2 ) terminal pairs simultaneously. Second, several barriers emerge when combining this static metric-MST paradigm with known dynamic data structures such as distance oracles, spanners, or tree embeddings.
Distance oracles and vertex sparsifiers. A first approach is to use a dynamic distance oracle to estimate pairwise terminal shortest-path distances. For an oracle of stretch ρ \rho ρ , querying all ( k 2 ) \binom{k}{2} ( 2 k ) terminal pairs reconstructs a ρ \rho ρ -approximate terminal metric on R R R . An MST of this graph estimates OPT G t ( R ) \operatorname{OPT}_{G_t}(R) OPT G t ( R ) within a 2 ρ 2\rho 2 ρ factor using O ~ ( k 2 ) \widetilde{O}(k^2) O ( k 2 ) distance queries. Plugging in the deterministic dynamic distance oracle of Haeupler, Long, and Saranurak (HLS) [HLS24], which for any fixed 0 < η < 1 0 < \eta< 1 0 < η < 1 achieves stretch ρ η = 2 poly ( 1 / η ) \rho_\eta= 2^{\operatorname{poly}(1/\eta)} ρ η = 2 poly ( 1/ η ) , we get O ( n η ) O(n^\eta) O ( n η ) worst-case update time and an O ( ρ η ) O(\rho_\eta) O ( ρ η ) -approximate cost query in O ~ ( k 2 ) \widetilde{O}(k^2) O ( k 2 ) time, since each distance query takes O η ( log log n ) O_\eta(\log\log n) O η ( log log n ) time.
To avoid querying all pairs, we can maintain a dynamic vertex sparsifier H t H_t H t on the terminal set R R R that preserves pairwise distances within stretch ρ \rho ρ , satisfying d G t ( u , v ) ≤ d H t ( u , v ) ≤ ρ d G t ( u , v ) d_{G_t}(u,v) \le d_{H_t}(u,v) \le\rho d_{G_t}(u,v) d G t ( u , v ) ≤ d H t ( u , v ) ≤ ρ d G t ( u , v ) for all u , v ∈ R u,v \in R u , v ∈ R . Running Mehlhorn’s linear-time terminal-MST construction directly on ( H t , R ) (H_t,R) ( H t , R ) computes an MST of K H t ( R ) K_{H_t}(R) K H t ( R ) in O ~ ( ∣ V ( H t ) ∣ + ∣ E ( H t ) ∣ ) \widetilde{O}(|V(H_t)|+|E(H_t)|) O ( ∣ V ( H t ) ∣ + ∣ E ( H t ) ∣ ) time, again yielding a 2 ρ 2\rho 2 ρ -approximate solution. Using the HLS vertex sparsifier [HLS24], we can maintain H t H_t H t of size O ( k n η ) O(kn^\eta) O ( k n η ) in O ( n η ) O(n^\eta) O ( n η ) amortized update time, reducing the cost-query time to O ~ ( k n η ) \widetilde{O}(kn^\eta) O ( k n η ) .
Both reductions support inexpensive O ( n η ) O(n^\eta) O ( n η ) -time updates to their distance structure, but computing a fresh Steiner cost still requires an MST computation, incurring O ~ ( k 2 ) \widetilde{O}(k^2) O ( k 2 ) or O ~ ( k n η ) \widetilde{O}(kn^\eta) O ( k n η ) time. Moreover, neither structure supports outputting an explicit Steiner tree in G t G_t G t directly.
Spanners and Mehlhorn’s construction. A second approach is to use a dynamic σ \sigma σ -spanner S t ⊆ G t S_t \subseteq G_t S t ⊆ G t , which is a sparse subgraph satisfying d G t ( u , v ) ≤ d S t ( u , v ) ≤ σ d G t ( u , v ) d_{G_t}(u,v) \le d_{S_t}(u,v) \le\sigma d_{G_t}(u,v) d G t ( u , v ) ≤ d S t ( u , v ) ≤ σ d G t ( u , v ) for all vertex pairs. Because S t S_t S t is an actual subgraph of G t G_t G t , running Mehlhorn’s construction on ( S t , R ) (S_t,R) ( S t , R ) yields an explicit 2 σ 2\sigma 2 σ -approximate Steiner tree in O ~ ( ∣ E ( S t ) ∣ + n ) \widetilde{O}(|E(S_t)|+n) O ( ∣ E ( S t ) ∣ + n ) time.
Using the deterministic dynamic spanner of Chuzhoy and Parter [CP25], which for any fixed 0 < ν < 1 0 < \nu< 1 0 < ν < 1 achieves worst-case size O ( n 1 + ν ) O(n^{1+\nu}) O ( n 1 + ν ) and stretch σ ν = 2 poly ( 1 / ν ) \sigma_\nu= 2^{\operatorname{poly}(1/\nu)} σ ν = 2 poly ( 1/ ν ) in O ( n ν ) O(n^\nu) O ( n ν ) amortized update time, gives O ( n ν ) O(n^\nu) O ( n ν ) update time and O ~ ( n 1 + ν ) \widetilde{O}(n^{1+\nu}) O ( n 1 + ν ) query time. The main drawback of this approach is that every query requires re-running Mehlhorn’s algorithm across all O ( n 1 + ν ) O(n^{1+\nu}) O ( n 1 + ν ) spanner edges, even when only an approximate cost is requested. Nonetheless, for reporting an explicit Steiner tree this bound is already near-linear, and our O ~ ( n 1 + ζ ) \widetilde{O}(n^{1+\zeta}) O ( n 1 + ζ ) tree-reporting guarantee is achieved by implementing this approach (see § 5.4 for details).
Tree embeddings. A third approach is to use a dynamic probabilistic dominating tree embedding, which is a rooted tree T T T with V ( G t ) ⊆ V ( T ) V(G_t) \subseteq V(T) V ( G t ) ⊆ V ( T ) satisfying d G t ( u , v ) ≤ d T ( u , v ) d_{G_t}(u,v) \le d_T(u,v) d G t ( u , v ) ≤ d T ( u , v ) for all u , v u,v u , v and expected stretch E [ d T ( u , v ) ] ≤ α d G t ( u , v ) \mathbb{E}[d_T(u,v)] \le\alpha d_{G_t}(u,v) E [ d T ( u , v )] ≤ α d G t ( u , v ) as G t G_t G t undergoes edge updates. On a single tree T T T , the minimum-weight subgraph connecting R R R is simply the unique minimal subtree spanning R R R , of weight C C C . Doubling this subtree and shortcutting between consecutive terminals yields a tour in K G t ( R ) K_{G_t}(R) K G t ( R ) of weight at most 2 C 2C 2 C , so noncontraction implies OPT G t ( R ) ≤ 2 C \operatorname{OPT}_{G_t}(R) \le2C OPT G t ( R ) ≤ 2 C , while routing an optimal Steiner tree of G t G_t G t through T T T gives E [ C ] ≤ α OPT G t ( R ) \mathbb{E}[C] \le\alpha\operatorname{OPT}_{G_t}(R) E [ C ] ≤ α OPT G t ( R ) by linearity of expectation. Augmenting this embedding with top trees [3 ] allows us to maintain the weight C C C of the minimal subtree spanning R R R , with O ( log n ) O(\log n) O ( log n ) overhead per change to the embedding, making the 2 α 2\alpha 2 α -approximate cost estimate 2 C 2C 2 C available in O ( 1 ) O(1) O ( 1 ) query time after every update.
Plugging in the dynamic probabilistic tree embeddings of Forster, Goranci, and Henzinger (FGH) [FGH21] yields an O ( log 5 n ) O(\log^5 n) O ( log 5 n ) -approximate cost estimate in expectation with n 1 / 2 + o ( 1 ) n^{1/2+o(1)} n 1/2 + o ( 1 ) expected amortized update time and O ( 1 ) O(1) O ( 1 ) query time. While this combination achieves sublinear update time and O ( 1 ) O(1) O ( 1 ) query time for arbitrary k k k , embedding a graph metric into a tree inevitably incurs Ω ( log n ) \Omega(\log n) Ω ( log n ) distortion, so the approximation factor is superconstant and the structure does not provide an explicit Steiner tree.
Table 1. Fully dynamic Steiner tree on k k k fixed terminals. All rows except FGH are deterministic.
An incremental framework
The main challenge is to maintain a constant-factor approximation with sublinear update time, independent of the number of terminals. To address it, we develop a framework that combines periodic global rebuilding with efficient local maintenance between rebuilds.
Periodic rebuilding. Our algorithm divides the update sequence into phases of B B B updates. At the beginning of each phase, we compute and freeze a global approximate solution. After each graph update, we defer global restructuring by combining these frozen structures with Steiner augmentation structures that adapt the maintained solution and preserve a bounded approximation across the phase. If a full global reconstruction incurs a cost of R \mathcal{R} R and the work for one update within a phase is at most U ( B ) \mathcal{U}(B) U ( B ) , the amortized cost per update is bounded by R / B + U ( B ) \mathcal{R}/B+\mathcal{U}(B) R / B + U ( B ) . Choosing the phase length B B B appropriately balances the heavy cost of periodic rebuilding against the per-update maintenance between rebuilds.
Route maintenance. At the start of the phase, we take a frozen snapshot S S S of a dynamic spanner S t S_t S t [BKS12] and run Mehlhorn’s construction on ( S , R ) (S,R) ( S , R ) to compute a terminal-metric MST T 0 T_0 T 0 , which is a constant approximation at the start of the phase and remains fixed throughout it, along with a static path-reporting distance oracle [TZ05] on S S S for querying frozen distances. We also record each vertex’s closest terminal a ( x ) ∈ R a(x) \in R a ( x ) ∈ R , called its owner, and its frozen owner distance δ ( x ) = d S ( a ( x ) , x ) \delta(x)=d_S(a(x),x) δ ( x ) = d S ( a ( x ) , x ) for later usage.
As edges are inserted, routes computed at the start of the phase remain valid, but new insertions may create cheaper connections. In the insertion-only setting, any newly useful route must encounter a newly inserted edge and hence one of its endpoints. To capture this, let F F F denote the set of at most B B B edges inserted during the phase, and maintain an auxiliary multigraph L F L_F L F on the O ( B ) O(B) O ( B ) endpoints of F F F . The edge set of L F L_F L F consists of two types of connections between these endpoints: virtual connections supplied by the frozen distance oracle (representing reusable old routes) and newly inserted edges with their actual weights (representing new routing opportunities). We maintain exact all-pairs shortest paths (APSP) on L F L_F L F to capture updated routing distances among these endpoints, combining old paths and new insertions. This routing information allows us to adapt the maintained terminal MST by incorporating new connections alongside the fixed baseline T 0 T_0 T 0 .
After each insertion, for each of the O ( B 2 ) O(B^2) O ( B 2 ) endpoint pairs x , y x,y x , y in L F L_F L F with distinct owners, we add or update a candidate edge between their owners a ( x ) a(x) a ( x ) and a ( y ) a(y) a ( y ) , weighted by δ ( x ) + d L F ( x , y ) + δ ( y ) \delta(x)+d_{L_F}(x,y)+\delta(y) δ ( x ) + d L F ( x , y ) + δ ( y ) . These candidate weights can only decrease, allowing a link–cut tree to maintain a terminal MST of the augmented graph T 0 ∪ C F T_0 \cup C_F T 0 ∪ C F consisting of T 0 T_0 T 0 and the candidate edges C F C_F C F in O ~ ( B 2 ) \widetilde{O}(B^2) O ( B 2 ) time per insertion. By the MST augmentation property (Lemma 2.10 ), augmenting T 0 T_0 T 0 rather than the full frozen terminal metric K S ( R ) K_S(R) K S ( R ) with C F C_F C F preserves the minimum spanning tree weight ( mst ( K S ( R ) ∪ C F ) = mst ( T 0 ∪ C F ) ) (\operatorname{mst}(K_S(R)\cup C_F)=\operatorname{mst}(T_0\cup C_F)) ( mst ( K S ( R ) ∪ C F ) = mst ( T 0 ∪ C F )) , while nearest-terminal ownership bounds the detour through endpoint owners (Lemma A.3), ensuring a constant-factor approximation throughout the phase (Theorem A.4 ). When an explicit Steiner tree is requested, we expand each selected terminal MST edge into its corresponding route in the current graph, using the stored frozen routes, inserted edges, and paths supplied by the distance oracle, and then take their union, remove cycles, and prune nonterminal leaves to obtain the solution. Balancing the O ~ ( n 1 + ζ / B ) \widetilde{O}(n^{1+\zeta}/B) O ( n 1 + ζ / B ) amortized phase-rebuild cost against the O ~ ( B 2 ) \widetilde{O}(B^2) O ( B 2 ) per-insertion work yields the O ~ ( n 2 / 3 + ζ ) \widetilde{O}(n^{2/3+\zeta}) O ( n 2/3 + ζ ) expected amortized update time of Theorem 1.2 .
Fully dynamic framework
Our fully dynamic algorithm in § 4 uses the same periodic rebuilding framework, combining frozen structures with Steiner augmentation structures. Supporting deletions, however, introduces two obstacles to our earlier approach: deleting a single graph edge invalidates all metric edges of T 0 T_0 T 0 whose underlying shortest paths use that edge, and it may destroy frozen routes in S S S used by the auxiliary multigraph L F L_F L F . We overcome both obstacles in sublinear deterministic time via four novel ingredients: (1) expanding T 0 T_0 T 0 into a single tree P 0 P_0 P 0 via coherent tree expansion so that any edge deletion breaks at most one tree edge, (2) recording both edge insertions and deletions on P 0 P_0 P 0 as zero-weight edges (spokes) to a virtual vertex (hub) in an auxiliary graph J t J_t J t , (3) identifying a surviving forest of O ( B ) O(B) O ( B ) components of P 0 P_0 P 0 by maintaining an exact minimum Steiner tree on J t J_t J t using dynamic programming on a top tree, and (4) reconnecting these O ( B ) O(B) O ( B ) surviving components in o ( n ) o(n) o ( n ) time by running Mehlhorn’s construction on a dynamic distance sparsifier.
Coherent tree expansion. At the beginning of each B B B -update phase on the phase-start graph G ∘ G^\circ G ∘ , we take a frozen copy S ⊆ G ∘ S \subseteq G^\circ S ⊆ G ∘ of the deterministic Chuzhoy–Parter dynamic σ ν \sigma_\nu σ ν -spanner S t S_t S t [CP25] and run Mehlhorn’s construction on ( S , R ) (S,R) ( S , R ) to obtain each vertex’s nearest terminal owner a ( x ) ∈ R a(x) \in R a ( x ) ∈ R , its owner distance δ ( x ) = d S ( a ( x ) , x ) \delta(x)=d_S(a(x),x) δ ( x ) = d S ( a ( x ) , x ) , the rooted owner forest, and a terminal-metric MST T 0 T_0 T 0 of K S ( R ) K_S(R) K S ( R ) . Each edge of T 0 T_0 T 0 corresponds to a shortest path in S S S between two terminals, and several such paths may share edges inside the owner forest. We then apply coherent tree expansion (Lemma 2.9 ) to expand T 0 T_0 T 0 along the rooted owner forest and deduplicate its shared edges into a single tree P 0 ⊆ S P_0 \subseteq S P 0 ⊆ S spanning R R R of weight w ( P 0 ) ≤ w ( T 0 ) ≤ 2 σ ν OPT G ∘ ( R ) w(P_0) \leq w(T_0) \leq2\sigma_\nu\operatorname{OPT}_{G^\circ}(R) w ( P 0 ) ≤ w ( T 0 ) ≤ 2 σ ν OPT G ∘ ( R ) . Working with P 0 P_0 P 0 rather than T 0 T_0 T 0 localizes structural damage: deleting an edge of G t G_t G t removes at most one edge of P 0 P_0 P 0 , even if several frozen routes in T 0 T_0 T 0 used it.
Hub-augmented auxiliary graph. As updates arrive, deletions may destroy routes in P 0 P_0 P 0 , while insertions may create cheaper paths. To adapt P 0 P_0 P 0 to these changes, we construct an auxiliary graph J t J_t J t that translates updates into virtual connections. We introduce an artificial vertex h h h , called hub , and virtual zero-cost edges, called spokes , incident to h h h . At the start of the phase, all edges of P 0 P_0 P 0 are enabled and all spokes are disabled. As updates occur, we update J t J_t J t as follows:
Deletion handling: Deleting u v ∈ E ( P 0 ) uv \in E(P_0) uv ∈ E ( P 0 ) disables u v uv uv in P 0 P_0 P 0 and enables the zero-weight spokes u h uh u h and v h vh v h at its endpoints, providing a zero-cost bridge across the broken route in P 0 P_0 P 0 .
Insertion handling: Inserting an edge u v uv uv enables the zero-weight spokes a ( u ) h a(u)h a ( u ) h and a ( v ) h a(v)h a ( v ) h at the endpoints’ terminal owners a ( u ) , a ( v ) ∈ R a(u),a(v) \in R a ( u ) , a ( v ) ∈ R on P 0 P_0 P 0 , providing a zero-cost connection through h h h that allows the algorithm to avoid expensive old routes in P 0 P_0 P 0 .
Letting D t ⊆ E ( P 0 ) D_t \subseteq E(P_0) D t ⊆ E ( P 0 ) denote the edges of P 0 P_0 P 0 deleted during the phase and A t ⊆ R A_t \subseteq R A t ⊆ R denote the active terminals (frozen owners of endpoints of newly inserted edges), the set of active vertices with enabled spokes is Z t = A t ∪ end ( D t ) ⊆ V ( P 0 ) Z_t=A_t \cup\operatorname{end}(D_t) \subseteq V(P_0) Z t = A t ∪ end ( D t ) ⊆ V ( P 0 ) of size O ( B ) O(B) O ( B ) , and the auxiliary graph is J t = ( P 0 − D t ) ∪ { z h : z ∈ Z t } J_t=(P_0-D_t)\cup\{zh:z\in Z_t\} J t = ( P 0 − D t ) ∪ { z h : z ∈ Z t } .
We maintain an exact minimum Steiner tree T t J T_t^J T t J connecting R R R in J t J_t J t and remove h h h and its selected spokes. This isolates which parts of P 0 P_0 P 0 are still worth keeping, leaving a forest F t = T t J − h ⊆ P 0 − D t F_t=T_t^J-h\subseteq P_0-D_t F t = T t J − h ⊆ P 0 − D t of retained P 0 P_0 P 0 components. Since a phase contains B B B updates and each update enables at most two spokes, F t F_t F t has at most O ( B ) O(B) O ( B ) components, reducing the repair task from connecting all k k k terminals to connecting at most O ( B ) O(B) O ( B ) components via current distances in G t G_t G t in O ~ ( B n η ) \widetilde{O}(Bn^\eta) O ( B n η ) time. Our analysis bounds the forest’s cost w ( F t ) w(F_t) w ( F t ) and the reconnection cost separately, showing that each is at most a constant multiple of OPT G t ( R ) \operatorname{OPT}_{G_t}(R) OPT G t ( R ) .
To see why J t J_t J t always contains a Steiner tree for R R R of weight at most 2 σ ν OPT G t ( R ) 2\sigma_\nu\operatorname{OPT}_{G_t}(R) 2 σ ν OPT G t ( R ) (Lemmas 4.5 and 4.6), consider removing all newly inserted edges from a minimum Steiner tree T ∗ T^* T ∗ in G t G_t G t , leaving components K ⊆ G ∘ K \subseteq G^\circ K ⊆ G ∘ that consist only of surviving phase-start edges. Rather than doubling all edges of a terminal-containing component K K K in a closed tour, we traverse K K K from an endpoint x ∈ V ( K ) x \in V(K) x ∈ V ( K ) of a removed newly inserted edge to a terminal r ∈ V ( K ) ∩ R r \in V(K)\cap R r ∈ V ( K ) ∩ R , traversing each edge on the unique x x x –r r r path in K K K once and every other edge of K K K twice, for a walk of length 2 w ( K ) − d K ( x , r ) 2w(K)-d_K(x,r) 2 w ( K ) − d K ( x , r ) . Because a ( x ) ∈ A t a(x)\in A_t a ( x ) ∈ A t is the nearest terminal to x x x in S S S , we have δ ( x ) ≤ d S ( r , x ) ≤ σ ν d K ( x , r ) \delta(x)\leq d_S(r,x)\leq\sigma_\nu d_K(x,r) δ ( x ) ≤ d S ( r , x ) ≤ σ ν d K ( x , r ) , so the subtraction along the x x x –r r r walk pays for the shortest path from a ( x ) a(x) a ( x ) to x x x in S S S . By the MST augmentation property (Lemma 2.10 ), the terminals of each component K K K together with a ( x ) a(x) a ( x ) can therefore be connected using routes in the frozen terminal metric K S ( R ) K_S(R) K S ( R ) of weight at most 2 σ ν w ( K ) 2\sigma_\nu w(K) 2 σ ν w ( K ) . Linking these components through their enabled owner spokes a ( x ) h a(x)h a ( x ) h —and bypassing any deleted edge u v ∈ D t uv\in D_t uv ∈ D t via its endpoint spokes u u u –h h h –v v v —yields a Steiner tree for R R R in J t J_t J t of weight at most ∑ K 2 σ ν w ( K ) ≤ 2 σ ν OPT G t ( R ) \sum_K 2\sigma_\nu w(K)\leq2\sigma_\nu\operatorname{OPT}_{G_t}(R) ∑ K 2 σ ν w ( K ) ≤ 2 σ ν OPT G t ( R ) .
Minimum Steiner tree maintenance on the hub-augmented tree. Exact optimization on J t J_t J t is enabled by its special “tree-plus-star” structure (§ 4.2 ): its non-spoke edges come from the fixed tree P 0 P_0 P 0 , while the virtual spokes form a star centered at h h h . At the start of the phase, we build a balanced top-tree hierarchy of clusters [AHdLT05] on the edges of P 0 P_0 P 0 of height O ( log n ) O(\log n) O ( log n ) exposing a fixed root terminal r 0 ∈ R r_0 \in R r 0 ∈ R , and run a static dynamic program (DP) to compute the initial optimal solution on J t J_t J t with all P 0 P_0 P 0 -edges enabled and all spokes disabled. Because each cluster C C C interacts with the rest of J t J_t J t through at most two boundary vertices ∂ C \partial C ∂ C in P 0 P_0 P 0 and h h h , each cluster has at most three interfaces I C = ∂ C ∪ { h } I_C = \partial C \cup\{h\} I C = ∂ C ∪ { h } and summarizes all partial solutions within C C C using a constant-size DP table of 22 states. The top-tree hierarchy built on P 0 P_0 P 0 stays fixed throughout the phase; only the availability of P 0 P_0 P 0 -edges and spokes changes due to graph updates. Toggling a P 0 P_0 P 0 -edge or spoke updates its assigned cluster’s local table and propagates changes up its ancestor path in the balanced hierarchy, recomputing O ( log n ) O(\log n) O ( log n ) tables in O ( 1 ) O(1) O ( 1 ) time each. Since each graph update toggles O ( 1 ) O(1) O ( 1 ) edges and spokes, maintaining the DP tables requires only O ( log n ) O(\log n) O ( log n ) time per update. Because the forest F t = T t J − h F_t = T_t^J - h F t = T t J − h may contain Θ ( n ) \Theta(n) Θ ( n ) edges, it is represented implicitly by the DP tables and backpointers (Lemma 4.3 ). We explain next how to use this implicit representation to extract one representative per component of F t F_t F t and reconnect those components in G t G_t G t .
Reconnecting surviving components. To reconnect the O ( B ) O(B) O ( B ) components of F t F_t F t into a Steiner tree for R R R , we select one representative vertex from each component and connect them in the current graph G t G_t G t (§ 4.3 ). For a candidate subgraph Y ⊆ J t Y \subseteq J_t Y ⊆ J t , by lexicographically minimizing
( w ( Y ) , number of selected spokes , number of selected edges ) , \left(w(Y),\ \text{number of selected spokes},\ \text{number of selected edges}\right), ( w ( Y ) , number of selected spokes , number of selected edges ) ,
the DP rules out unnecessary zero-weight spokes and terminal-free components, guaranteeing that every component of F t F_t F t contains at least one terminal in R R R and is incident to a unique selected spoke to h h h (Lemma 4.1 ). Following the DP backpointers from the root only into clusters with selected spokes, we find the set Q t ⊆ Z t ∪ { r 0 } Q_t \subseteq Z_t \cup\{r_0\} Q t ⊆ Z t ∪ { r 0 } of these O ( B ) O(B) O ( B ) spoke endpoints in O ( B log n ) O(B \log n) O ( B log n ) time. Because each component of F t F_t F t already connects its terminals to its representative in Q t Q_t Q t , connecting Q t Q_t Q t in G t G_t G t suffices to connect R R R . Moreover, since every component of F t F_t F t contains a terminal in R R R , the union of F t F_t F t with an optimal Steiner tree for R R R in G t G_t G t connects all vertices of Q t Q_t Q t , proving that OPT G t ( Q t ) ≤ w ( F t ) + OPT G t ( R ) ≤ ( 1 + 2 σ ν ) OPT G t ( R ) \operatorname{OPT}_{G_t}(Q_t) \leq w(F_t) + \operatorname{OPT}_{G_t}(R) \leq(1 + 2\sigma_\nu)\operatorname{OPT}_{G_t}(R) OPT G t ( Q t ) ≤ w ( F t ) + OPT G t ( R ) ≤ ( 1 + 2 σ ν ) OPT G t ( R ) (Lemma 4.7).
To preserve approximate distances among Q t Q_t Q t , we maintain the deterministic HLS distance sparsifier H t H_t H t [HLS24] (Theorem 2.5) on the monotonically growing superset U t = Z t ∪ { r 0 } ⊇ Q t U_t = Z_t \cup\{r_0\} \supseteq Q_t U t = Z t ∪ { r 0 } ⊇ Q t of all O ( B ) O(B) O ( B ) active vertices accumulated during the phase. Because U t U_t U t gains up to two newly active vertices per graph update and is reset to { r 0 } \{r_0\} { r 0 } at phase boundaries, updating U t U_t U t in H t H_t H t takes O ( n η ) O(n^\eta) O ( n η ) amortized time per update and keeps ∣ V ( H t ) ∣ + ∣ E ( H t ) ∣ = O ( ∣ U t ∣ n η ) = O ( B n η ) |V(H_t)| + |E(H_t)| = O(|U_t|n^\eta) = O(Bn^\eta) ∣ V ( H t ) ∣ + ∣ E ( H t ) ∣ = O ( ∣ U t ∣ n η ) = O ( B n η ) (Lemma 4.4 ). By contrast, maintaining H t H_t H t on Q t Q_t Q t directly would be slower, as a single edge update can cause the top-tree DP to switch which components connect to the hub and change Ω ( B ) \Omega(B) Ω ( B ) vertices of Q t Q_t Q t at once. After each update, we run Melhorn’s construction on ( H t , Q t ) (H_t,Q_t) ( H t , Q t ) in O ~ ( B n η ) \widetilde{O}(Bn^\eta) O ( B n η ) deterministic time to compute a terminal-metric MST on Q t Q_t Q t , whose weight (scaled by σ ν \sigma_\nu σ ν ) combined with w ( F t ) w(F_t) w ( F t ) provides our O ( 1 ) O(1) O ( 1 ) -time cost estimate (Theorem 4.9 ). Combining the phase-reconstruction time O ~ ( n 1 + ν − η / B ) + O ( n η ) \widetilde{O}(n^{1+\nu-\eta}/B) + O(n^\eta) O ( n 1 + ν − η / B ) + O ( n η ) with the single-update processing time O ( n ν ) + O ~ ( B n η ) O(n^\nu) + \widetilde{O}(Bn^\eta) O ( n ν ) + O ( B n η ) gives amortized update time
T u p d ( B ) = O ~ ( n 1 + ν B + n ν + B n η ) . T_{\mathrm{upd}}(B) = \widetilde{O}\left(\frac{n^{1+\nu}}{B} + n^\nu+ Bn^\eta\right). T upd ( B ) = O ( B n 1 + ν + n ν + B n η ) .
which we balance by setting B = ⌈ n ( 1 + ν − η ) / 2 ⌉ B = \lceil n^{(1+\nu-\eta)/2}\rceil B = ⌈ n ( 1 + ν − η ) /2 ⌉ to obtain O ~ ( n ( 1 + ν + η ) / 2 ) \widetilde{O}(n^{(1+\nu+\eta)/2}) O ( n ( 1 + ν + η ) /2 ) deterministic amortized update time, i.e., O ~ ( n 1 / 2 + ζ ) \widetilde{O}(n^{1/2+\zeta}) O ( n 1/2 + ζ ) for ν = η = ζ \nu= \eta= \zeta ν = η = ζ (Theorem 1.1 ).
Related Work
We review dynamic Steiner-tree algorithms across several update models, including graph-edge updates and changes to terminals or demands in a fixed metric. We then discuss dynamic graph primitives relevant to our approach and the Steiner cost-estimation bounds that follow from straightforward combinations of these tools.
Steiner trees under graph-edge updates. Several algorithms maintain approximate Steiner trees under changes to the underlying graph, providing the closest comparisons to our setting. Bergamaschi et al. [BHPG+21] maintain a ( 2 + ε ) (2+\varepsilon) ( 2 + ε ) -approximate Steiner tree in unweighted graphs under both edge and terminal updates, with high probability against an oblivious adversary. For k k k terminals, their worst-case edge-update time is O ( n 1.529 + k 2 n 1 + o ( 1 ) ) O(n^{1.529}+k^2n^{1+o(1)}) O ( n 1.529 + k 2 n 1 + o ( 1 ) ) , including the time to report an explicit tree. Raikwar and Karmakar [RK23] give an incremental algorithm for weighted general graphs achieving a ( 2 − ε ) (2-\varepsilon) ( 2 − ε ) -approximation with O ( n ) O(n) O ( n ) update time. Subsequently, Raikwar, Sadhakarіya, and Karmakar [RSK25] give a ( 2 − ε ) (2-\varepsilon) ( 2 − ε ) -approximate incremental algorithm for weighted general graphs with O ( n D s ) O(nD_s) O ( n D s ) update time, where D s D_s D s is the maximum number of edges on a weighted shortest path. They also give a ( 2 + ε ) (2+\varepsilon) ( 2 + ε ) -approximate fully dynamic algorithm for weighted planar graphs, processing a batch of b b b updates in O ~ ( k 2 n + k D + n ) \widetilde{O}(k^2\sqrt{n}+kD+n) O ( k 2 n + k D + n ) time for 1 ≤ b ≤ n + m 1\le b\le\sqrt{n+m} 1 ≤ b ≤ n + m , where D D D is the unweighted diameter of the graph.
Terminal updates, online recourse, and geometric variants. A separate line of work keeps the underlying graph fixed while allowing terminals or connection requirements to change. In a fixed underlying graph, Łącki et al. [ŁOP+15] obtain a ( 6 + ε ) (6+\varepsilon) ( 6 + ε ) -approximation with O ~ ( n log D ) \widetilde{O}(\sqrt{n}\log D) O ( n log D ) amortized time per terminal insertion or deletion, where D D D is the metric aspect ratio. Online models often emphasize competitiveness and recourse , the number of changes to the maintained solution. This line includes Imase and Waxman [IW91], constant-competitive Steiner trees with constant recourse under arrivals [GGK13], and constant amortized recourse under terminal arrivals and departures [GK14]. For Steiner forest, Long et al. [LMST26] obtain constant competitiveness with logarithmic amortized recourse per arriving demand pair. In fixed-dimensional Euclidean space, Chan et al. [CGJ+24] maintain an implicit ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -approximate Steiner tree with polylogarithmic amortized update time for fixed dimension and ε \varepsilon ε .
Dynamic minimum spanning trees. Dynamic MST is the all-terminal special case of our problem and a component of our incremental algorithm. Beyond the classical progression from Frederickson [Fre85] through sparsification [EGIN92, EGIN97] to deterministic O ( log 4 n ) O(\log^4 n) O ( log 4 n ) amortized updates [HdLT01], Holm, Rotenberg, and Wulff-Nilsen [HRWN15] improved the deterministic amortized bound to O ( log 4 n / log log n ) O(\log^4 n/\log\log n) O ( log 4 n / log log n ) . For worst-case updates, Kapron, King, and Mountjoy [KKM13] obtained polylogarithmic Monte Carlo bounds against an oblivious adversary; against an adaptive adversary, Nanongkai, Saranurak, and Wulff-Nilsen [NSWN17] achieved n o ( 1 ) n^{o(1)} n o ( 1 ) worst-case update time w.h.p., Chuzhoy et al. [CGL+20] made this n o ( 1 ) n^{o(1)} n o ( 1 ) worst-case bound deterministic, and Meierhans, Probst Gutenberg, and Yeh [MPGY26] recently achieved polylogarithmic worst-case update time w.h.p.
Dynamic spanners. Dynamic spanners reduce the cost of our periodic rebuilds by preserving approximate distances in sparse subgraphs [PS89, ADD+93, BS07]. Following early dynamic constructions [2 Elk07] , Baswana, Khurana, and Sarkar [BKS12] obtained ( 2 s − 1 ) (2s-1) ( 2 s − 1 ) -spanners of size O ~ ( n 1 + 1 / s ) \widetilde{O}(n^{1+1/s}) O ( n 1 + 1/ s ) in polylogarithmic expected amortized update time against an oblivious adversary, which we combine with geometric weight bucketing in our insertion-only algorithm. Subsequent work achieved faster amortized maintenance [FG19], sublinear worst-case update time [BK16, BFH21], and adaptive-adversary or deterministic guarantees [BvdBPG+22, BSS22, vdBCK+23], culminating in the deterministic constant-stretch spanners of Chuzhoy and Parter [CP25] via low-diameter router decompositions, which we use in our fully dynamic algorithm. Preserving distances alone, however, does not maintain a low-cost connection among the terminals; our use of sparsification is therefore coupled with periodic rebuilding and an optimizer for the retained solution.
Distance oracles and terminal sparsifiers. Distance oracles and terminal sparsifiers supply the distance and path information used to construct and repair terminal connections in our algorithms. Thorup–Zwick oracles [TZ05] supply the static distance interface in our incremental algorithm. Fully dynamic constant-stretch oracles include the randomized construction of Forster et al. [FGNS23] and the deterministic construction of Haeupler, Long, and Saranurak (HLS) [HLS24]. For fixed η > 0 \eta> 0 η > 0 , HLS achieve stretch A η = 2 poly ( 1 / η ) A_{\eta} = 2^{\operatorname{poly}(1/\eta)} A η = 2 poly ( 1/ η ) , O ( n η ) O(n^{\eta}) O ( n η ) worst-case update time, and O η ( log log n ) O_{\eta}(\log\log n) O η ( log log n ) distance-query time. Their separate terminal-sparsifier maintains a graph H H H of size O ( k n η ) O(kn^{\eta}) O ( k n η ) preserving terminal distances within A η A_{\eta} A η , in O ( n η ) O(n^{\eta}) O ( n η ) amortized update time. Kyng, Meierhans, and Probst Gutenberg [KMPG24] give a complementary deterministic construction with subpolynomial stretch and worst-case update time, together with low-congestion embeddings.
Tree embeddings and cost estimates. Dynamic tree embeddings provide another route to Steiner cost estimation by approximating a graph’s metric with a tree metric. While probabilistic tree embeddings were pioneered in the static setting by Bartal [4 Bar98] and subsequently refined with optimal O ( log n ) O(\log n) O ( log n ) distortion bounds by Fakcharoenphol, Rao, and Talwar [FRT04], maintaining such metric approximations dynamically under edge updates has long proved challenging. Forster, Goranci, and Henzinger (FGH) [FGH21] advanced this frontier by designing dynamic algorithms for maintaining low-stretch probabilistic tree embeddings under edge updates, applying them to problems such as buy-at-bulk network design. Nevertheless, while black-box tree embeddings offer flexible metric reductions, translating tree-based solutions back into valid graph paths while guaranteeing sublinear update times and tight constant-factor approximations for fully dynamic Steiner tree remains difficult, motivating our direct structural and sparsification-based approach.
Organization. § 2 presents the model and assumptions, algorithmic primitives, and terminal-metric MST tools. § 3 introduces the insertion-only framework as a warm-up, with implementation details and analysis deferred to Appendix § 6 . § 4 develops the fully dynamic algorithm and establishes its approximation, time, and space guarantees.
Preliminaries
We first specify the graph model, weight assumptions, and how the maintained solution is represented. We then state the external spanner and distance primitives used by our algorithms. § 2.3 develops the terminal-MST construction and its properties, used by both algorithms.
Model and Assumptions
Graph and update model. Let G t = ( V , R , E t , w t ) G_t = (V, R, E_t, w_t) G t = ( V , R , E t , w t ) be an undirected graph on a fixed vertex set V V V , ∣ V ∣ = n |V| = n ∣ V ∣ = n , with a fixed terminal set R ⊆ V R \subseteq V R ⊆ V , ∣ R ∣ = k ≥ 2 |R| = k \ge2 ∣ R ∣ = k ≥ 2 . All edge weights are strictly positive. Write m 0 m_0 m 0 for the initial edge count and m t m_t m t for the current edge count; m m m is an upper bound on the total edge count throughout. We assume that the update sequence has polynomial length in n n n .
The fully dynamic algorithm supports edge insertions, deletions, and weight changes (a weight change is processed internally by deleting the old edge and inserting a new edge with the updated weight, without affecting correctness or bounds), and is deterministic (thus holding against an adaptive adversary). The incremental algorithm supports only edge insertions and is randomized, with amortized update time bounded in expectation against an oblivious adversary. We assume that the initial graph and the graph resulting from each update are connected. Both algorithms always return a valid solution with the stated approximation guarantee. The notation O ~ \widetilde{O} O suppresses polylogarithmic factors in n n n .
Weights. We assume that all input weights throughout the update sequence lie in [ 1 , W ] [1,W] [ 1 , W ] , where W = n O ( 1 ) W = n^{O(1)} W = n O ( 1 ) . For some 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 , the fully dynamic algorithm uses rounded edge weights
w ^ ( e ) = ⌈ w ( e ) ε ⌉ . (1) \widehat{w}(e) = \left\lceil\frac{w(e)}{\varepsilon} \right\rceil. \tag*{(1)} w ( e ) = ⌈ ε w ( e ) ⌉ . (1)
The effect of this rounding on the approximation ratio is analyzed in Lemma 4.10.
Notation. For a weighted graph Q Q Q , let d Q d_Q d Q denote shortest-path distance and let OPT Q ( U ) \operatorname{OPT}_Q(U) OPT Q ( U ) be the minimum weight of a connected subgraph containing a specified vertex set U U U . With nonnegative weights, cycles can be removed without increasing the cost, so OPT Q ( U ) \operatorname{OPT}_Q(U) OPT Q ( U ) is also the minimum weight of a Steiner tree connecting U U U . We write mst ( Q ) \operatorname{mst}(Q) mst ( Q ) for the weight of a minimum spanning tree of Q Q Q .
The terminal metric closure K Q ( U ) K_Q(U) K Q ( U ) is the complete graph on U U U with edge weight d Q ( u , v ) d_Q(u,v) d Q ( u , v ) . For a tree T T T on U U U , we write
w K Q ( U ) ( T ) = ∑ u v ∈ E ( T ) d Q ( u , v ) . w_{K_Q(U)}(T) = \sum_{uv \in E(T)} d_Q(u,v). w K Q ( U ) ( T ) = uv ∈ E ( T ) ∑ d Q ( u , v ) .
Maintained Output. After each update, our algorithms maintain the approximate Steiner tree implicitly by storing a compact representation of the solution (along with its cost estimation, which can be read in O ( 1 ) O(1) O ( 1 ) time) that, with additional reporting time, can be expanded to retrieve an explicit Steiner tree in G t G_t G t . Our update-time bounds refer to maintaining the implicit solution. Reporting a solution explicitly incurs additional time that is analyzed separately. Note that the cost of reporting the approximate solution can be Ω ( n ) \Omega(n) Ω ( n ) , since an optimal Steiner tree may contain Θ ( n ) \Theta(n) Θ ( n ) edges.
Algorithmic Primitives
We introduce several dynamic graph primitives used by our algorithms and adapt their interfaces to our setting. Our insertion-only algorithm pairs BKS’s randomized fully dynamic weighted spanner [BKS12] with the static path-reporting distance oracle of Thorup and Zwick [TZ05], while our fully dynamic algorithm pairs the deterministic dynamic spanner of Chuzhoy and Parter [CP25] with the deterministic dynamic distance sparsifier of Haeupler, Long, and Saranurak [HLS24].
Fully dynamic weighted spanners. A spanner is a subgraph that approximately preserves distances in the original graph. In our insertion-only algorithm, we use a weighted extension of BKS’s randomized spanner [BKS12] to maintain a sparse graph under edge updates.
Theorem 2.1. Fix an integer s ≥ 2 s \ge2 s ≥ 2 and a constant 0 < δ < 1 0 < \delta< 1 0 < δ < 1 . For undirected graphs with a polynomially bounded edge-weight ratio over the entire update sequence, a randomized fully dynamic structure maintains an explicit subgraph S t ⊆ G t S_t \subseteq G_t S t ⊆ G t such that
d G t ( u , v ) ≤ d S t ( u , v ) ≤ σ d G t ( u , v ) , σ = ( 2 s − 1 ) ( 1 + δ ) . d_{G_t}(u,v) \le d_{S_t}(u,v) \le\sigma d_{G_t}(u,v), \qquad\sigma= (2s-1)(1+\delta). d G t ( u , v ) ≤ d S t ( u , v ) ≤ σ d G t ( u , v ) , σ = ( 2 s − 1 ) ( 1 + δ ) . The expected size is O ~ ( s n 1 + 1 / s ) \widetilde{O}(sn^{1+1/s}) O ( s n 1 + 1/ s ) , and the expected amortized update time is O ~ ( s 2 ) \widetilde{O}(s^2) O ( s 2 ) against an oblivious update sequence. The stretch guarantee holds deterministically. Starting from m 0 m_0 m 0 edges, initialization takes O ~ ( n + s 2 m 0 ) \widetilde{O}(n+s^2m_0) O ( n + s 2 m 0 ) time.
Proof Sketch. For unweighted graphs, [BKS12] maintains a ( 2 s − 1 ) (2s-1) ( 2 s − 1 ) -spanner of expected size O ( s n 1 + 1 / s log n ) O(sn^{1+1/s}\log n) O ( s n 1 + 1/ s log n ) in O ( s 2 log 2 n ) O(s^2\log^2 n) O ( s 2 log 2 n ) expected amortized time per edge insertion or deletion. Following [BKS12, Remark 1.2], we partition the edges into O ( log 1 + δ ( w max / w min ) ) = O ( log n ) O(\log_{1+\delta}(w_{\max}/w_{\min})) = O(\log n) O ( log 1 + δ ( w m a x / w m i n )) = O ( log n ) weight buckets with ratio 1 + δ 1+\delta 1 + δ and maintain an unweighted ( 2 s − 1 ) (2s-1) ( 2 s − 1 ) -spanner within each bucket; their union achieves weighted stretch ( 2 s − 1 ) ( 1 + δ ) (2s-1)(1+\delta) ( 2 s − 1 ) ( 1 + δ ) at the cost of an O ( log n ) O(\log n) O ( log n ) factor in size and update time, absorbed in O ~ \widetilde{O} O . Initializing the O ( log n ) O(\log n) O ( log n ) empty bucket structures on n n n vertices and inserting the m 0 m_0 m 0 initial edges takes expected O ~ ( n + s 2 m 0 ) \widetilde{O}(n+s^2m_0) O ( n + s 2 m 0 ) time, and weight changes are handled by deleting and reinserting the edge.
For our fully dynamic algorithm, we use the deterministic weighted spanner of Chuzhoy and Parter [CP25].
Theorem 2.2. For any fixed 0 < ν < 1 0 < \nu< 1 0 < ν < 1 and an undirected n n n -vertex graph G t G_t G t with polynomially bounded positive integer edge weights over the entire update sequence, a deterministic fully dynamic data structure maintains an explicit subgraph S t ⊆ G t S_t \subseteq G_t S t ⊆ G t satisfying
d G t ( u , v ) ≤ d S t ( u , v ) ≤ σ ν d G t ( u , v ) , d_{G_t}(u,v) \le d_{S_t}(u,v) \le\sigma_\nu d_{G_t}(u,v), d G t ( u , v ) ≤ d S t ( u , v ) ≤ σ ν d G t ( u , v ) , with worst-case size ∣ E ( S t ) ∣ = O ( n 1 + ν ) |E(S_t)| = O(n^{1+\nu}) ∣ E ( S t ) ∣ = O ( n 1 + ν ) , amortized update time O ( n ν ) O(n^\nu) O ( n ν ) , initialization time O ( ( m 0 + n ) n ν ) O((m_0+n)n^\nu) O (( m 0 + n ) n ν ) from m 0 m_0 m 0 initial edges, and space O ( m t n ν + n 1 + ν ) O(m_tn^\nu+n^{1+\nu}) O ( m t n ν + n 1 + ν ) , where m t = ∣ E ( G t ) ∣ m_t = |E(G_t)| m t = ∣ E ( G t ) ∣ and the stretch σ ν = 2 poly ( 1 / ν ) \sigma_\nu= 2^{\operatorname{poly}(1/\nu)} σ ν = 2 poly ( 1/ ν ) depends only on ν \nu ν .
Proof Sketch. By [CP25, Corollary 9.2], for integer parameters 512 ≤ k ≤ ( log n ) 1 / 49 512 \le k \le(\log n)^{1/49} 512 ≤ k ≤ ( log n ) 1/49 and 1 / δ C P ∈ [ 400 , k ] 1/\delta_{\mathrm{CP}} \in[400,k] 1/ δ CP ∈ [ 400 , k ] , an initially empty n n n -vertex simple graph undergoing at most n 2 n^2 n 2 edge insertions and deletions with integer weights in { 1 , … , W ′ } \{1,\ldots,W'\} { 1 , … , W ′ } admits a deterministic dynamic spanner of stretch k 19 ⋅ 2 O ( 1 / δ C P 6 ) k^{19}\cdot2^{O(1/\delta_{\mathrm{CP}}^6)} k 19 ⋅ 2 O ( 1/ δ CP 6 ) and worst-case size O ( n 1 + O ( 1 / k ) log W ′ ) O(n^{1+O(1/k)}\log W') O ( n 1 + O ( 1/ k ) log W ′ ) in n O ( δ C P ) n^{O(\delta_{\mathrm{CP}})} n O ( δ CP ) worst-case update time. Given a fixed 0 < ν < 1 0 < \nu< 1 0 < ν < 1 , we choose integers 1 / δ C P = Θ ( 1 / ν ) ≥ 400 1/\delta_{\mathrm{CP}} = \Theta(1/\nu) \ge400 1/ δ CP = Θ ( 1/ ν ) ≥ 400 and k = max { 1 / δ C P , Θ ( 1 / ν ) } ≥ 512 k = \max\{1/\delta_{\mathrm{CP}},\Theta(1/\nu)\} \ge512 k = max { 1/ δ CP , Θ ( 1/ ν )} ≥ 512 sufficiently large so that the n O ( δ C P ) n^{O(\delta_{\mathrm{CP}})} n O ( δ CP ) update time is O ( n ν ) O(n^\nu) O ( n ν ) and, since log W ′ = O ( log n ) \log W' = O(\log n) log W ′ = O ( log n ) , the O ( n 1 + O ( 1 / k ) log W ′ ) O(n^{1+O(1/k)}\log W') O ( n 1 + O ( 1/ k ) log W ′ ) size bound is O ( n 1 + ν / 2 log n ) = O ( n 1 + ν ) O(n^{1+\nu/2}\log n) = O(n^{1+\nu}) O ( n 1 + ν /2 log n ) = O ( n 1 + ν ) , giving σ ν = 2 O ( 1 / ν ) \sigma_\nu= 2^{O(1/\nu)} σ ν = 2 O ( 1/ ν ) . Re-initializing the structure from scratch every max { ⌈ m ′ / 4 ⌉ , n } \max\{\lceil m'/4\rceil,n\} max {⌈ m ′ /4 ⌉ , n } updates (where m ′ m' m ′ is the edge count at the last rebuild, so at most m ′ + 2 max { ⌈ m ′ / 4 ⌉ , n } < n 2 m' + 2\max\{\lceil m'/4\rceil,n\} < n^2 m ′ + 2 max {⌈ m ′ /4 ⌉ , n } < n 2 edge operations occur between rebuilds) extends the guarantee to arbitrary m 0 m_0 m 0 and polynomial-length update sequences with O ( n ν ) O(n^\nu) O ( n ν ) amortized update overhead and O ( m t n ν + n 1 + ν ) O(m_tn^\nu+n^{1+\nu}) O ( m t n ν + n 1 + ν ) space.
Static path-reporting distance oracle. Our insertion-only algorithm uses the static path-reporting distance oracle of Thorup and Zwick [TZ05]:
Theorem 2.3 ([TZ05]). For an integer r ≥ 2 r \ge2 r ≥ 2 , an undirected weighted n n n -vertex graph G G G with M M M edges admits expected preprocessing time O ~ ( r M n 1 / r ) \widetilde{O}(rMn^{1/r}) O ( r M n 1/ r ) and expected space O ~ ( r n 1 + 1 / r ) \widetilde{O}(rn^{1+1/r}) O ( r n 1 + 1/ r ) . For any connected pair x , y x,y x , y , a query takes O ~ ( r ) \widetilde{O}(r) O ( r ) time and returns an estimate satisfying
d G ( x , y ) ≤ d ^ G ( x , y ) ≤ ( 2 r − 1 ) d G ( x , y ) . d_G(x,y) \le\widehat{d}_G(x,y) \le(2r-1)d_G(x,y). d G ( x , y ) ≤ d G ( x , y ) ≤ ( 2 r − 1 ) d G ( x , y ) .
On request, it reports a simple path of weight at most this estimate in O ~ ( r + ℓ ) \widetilde{O}(r+\ell) O ( r + ℓ ) time, where ℓ \ell ℓ is the number of reported edges.
HLS distance sparsifiers. We use the dynamic distance sparsifier of Haeupler, Long, and Saranurak [HLS24]—a smaller weighted graph that preserves approximate distances among vertices from a designated set. Unlike a spanner, this object need not be a subgraph of the original graph, and it may contain auxiliary vertices and edges. Let us first recall their result. We write θ \theta θ for their parameter ϵ \epsilon ϵ .
Theorem 2.4 ([HLS24, Theorem 13.1(1)]). For some absolute constant c > 0 c > 0 c > 0 , any parameter 1 / log c n ≤ θ ≤ 1 1/\log^{c} n \leq\theta\leq1 1/ log c n ≤ θ ≤ 1 , and an undirected n n n -vertex graph with polynomially bounded positive integer weights, there is a deterministic data structure maintaining an explicit sparsifier H t H_t H t for a designated vertex set U t U_t U t , satisfying
d G t ( u , v ) α l o w ( θ ) ≤ d H t ( u , v ) ≤ α u p ( θ ) d G t ( u , v ) ( u , v ∈ U t ) , \frac{d_{G_t}(u,v)}{\alpha_{\mathrm{low}}(\theta)} \leq d_{H_t}(u,v) \leq\alpha_{\mathrm{up}}(\theta)d_{G_t}(u,v) \qquad(u,v \in U_t), α low ( θ ) d G t ( u , v ) ≤ d H t ( u , v ) ≤ α up ( θ ) d G t ( u , v ) ( u , v ∈ U t ) , with size ∣ U t ∣ n O ( θ 4 ) |U_t|n^{O(\theta^4)} ∣ U t ∣ n O ( θ 4 ) , amortized update time n O ( θ ) n^{O(\theta)} n O ( θ ) per edge or designated-vertex insertion or deletion, and initialization time ( m 0 + n ) n O ( θ ) (m_0+n)n^{O(\theta)} ( m 0 + n ) n O ( θ ) , where the approximation factors α l o w ( θ ) , α u p ( θ ) = 2 poly ( 1 / θ ) \alpha_{\mathrm{low}}(\theta),\alpha_{\mathrm{up}}(\theta)=2^{\operatorname{poly}(1/\theta)} α low ( θ ) , α up ( θ ) = 2 poly ( 1/ θ ) depend only on θ \theta θ .
We make some slight modifications to their result to simplify its later usage.
Theorem 2.5 (cf. [HLS24]). For any fixed 0 < η < 1 0 < \eta< 1 0 < η < 1 and an undirected n n n -vertex graph G t G_t G t with polynomially bounded positive integer weights, there is a deterministic data structure maintaining an explicit sparsifier H t H_t H t with positive edge weights for a designated vertex set U t ⊆ V U_t \subseteq V U t ⊆ V , satisfying
d G t ( u , v ) ≤ d H t ( u , v ) ≤ ρ η d G t ( u , v ) ( u , v ∈ U t ) , d_{G_t}(u,v) \leq d_{H_t}(u,v) \leq\rho_\eta d_{G_t}(u,v) \qquad(u,v \in U_t), d G t ( u , v ) ≤ d H t ( u , v ) ≤ ρ η d G t ( u , v ) ( u , v ∈ U t ) , with size ∣ V ( H t ) ∣ + ∣ E ( H t ) ∣ = O ( ∣ U t ∣ n η ) |V(H_t)|+|E(H_t)|=O(|U_t|n^\eta) ∣ V ( H t ) ∣ + ∣ E ( H t ) ∣ = O ( ∣ U t ∣ n η ) , amortized update time O ( n η ) O(n^\eta) O ( n η ) per edge or designated-vertex insertion or deletion, initialization time O ( ( m 0 + n ) n η ) O((m_0+n)n^\eta) O (( m 0 + n ) n η ) , and space O ( ( m t + n ) n η ) O((m_t+n)n^\eta) O (( m t + n ) n η ) , where m t = ∣ E ( G t ) ∣ m_t=|E(G_t)| m t = ∣ E ( G t ) ∣ and the approximation factor ρ η = 2 poly ( 1 / η ) \rho_\eta=2^{\operatorname{poly}(1/\eta)} ρ η = 2 poly ( 1/ η ) depends only on η \eta η .
Proof Sketch. Given a fixed 0 < η < 1 0 < \eta< 1 0 < η < 1 , we choose θ = Θ ( η ) ∈ ( 0 , 1 ) \theta=\Theta(\eta)\in(0,1) θ = Θ ( η ) ∈ ( 0 , 1 ) sufficiently small so that the n O ( θ 4 ) n^{O(\theta^4)} n O ( θ 4 ) and n O ( θ ) n^{O(\theta)} n O ( θ ) factors in Theorem 2.4 are bounded by O ( n η ) O(n^\eta) O ( n η ) . Scaling all edge weights of H t H_t H t by α l o w ( θ ) \alpha_{\mathrm{low}}(\theta) α low ( θ ) ensures noncontraction ( d G t ( u , v ) ≤ d H t ( u , v ) ≤ ρ η d G t ( u , v ) ) (d_{G_t}(u,v)\leq d_{H_t}(u,v)\leq\rho_\eta d_{G_t}(u,v)) ( d G t ( u , v ) ≤ d H t ( u , v ) ≤ ρ η d G t ( u , v )) with ρ η = α l o w ( θ ) α u p ( θ ) = 2 poly ( 1 / η ) \rho_\eta=\alpha_{\mathrm{low}}(\theta)\alpha_{\mathrm{up}}(\theta)=2^{\operatorname{poly}(1/\eta)} ρ η = α low ( θ ) α up ( θ ) = 2 poly ( 1/ η ) . Re-initializing the structure from scratch on ( G t , U t ) (G_t,U_t) ( G t , U t ) every L = max { ⌈ m ′ / 4 ⌉ , n } L=\max\{\lceil m'/4\rceil,n\} L = max {⌈ m ′ /4 ⌉ , n } operations (where m ′ m' m ′ is the edge count at initialization or the last rebuild, so m ′ + n + L = O ( m t + n ) m'+n+L=O(m_t+n) m ′ + n + L = O ( m t + n ) throughout the window and the O ( ( m ′ + L + n ) n η ) = O ( L n η ) O((m'+L+n)n^\eta)=O(Ln^\eta) O (( m ′ + L + n ) n η ) = O ( L n η ) rebuild cost charges O ( n η ) O(n^\eta) O ( n η ) per operation) bounds the total work—and hence space—of the active instance by O ( ( m t + n ) n η ) O((m_t+n)n^\eta) O (( m t + n ) n η ) .
Terminal-Metric MSTs
We introduce several basic concepts and constructions used to approximate the Steiner tree. A classical approach to approximating the Steiner tree [KMB81] reduces finding a Steiner tree for a terminal set U U U in Q Q Q to computing an MST of the terminal metric closure K Q ( U ) K_Q(U) K Q ( U ) and unfolding its edges into shortest paths in Q Q Q , losing at most a factor of 2.
Lemma 2.6 (Metric MST). For a connected graph Q Q Q with positive edge weights and a nonempty terminal set U ⊆ V ( Q ) U \subseteq V(Q) U ⊆ V ( Q ) ,
mst ( K Q ( U ) ) ≤ 2 OPT Q ( U ) , \operatorname{mst}(K_Q(U)) \le2\operatorname{OPT}_Q(U), mst ( K Q ( U )) ≤ 2 OPT Q ( U ) , that is, the weight of an MST of the terminal metric closure is at most twice the weight of an optimal Steiner tree connecting U U U in Q Q Q . Moreover, replacing each edge of a spanning tree of K Q ( U ) K_Q(U) K Q ( U ) by a shortest path in Q Q Q and taking the union of these paths yields a connected subgraph containing U U U , whose weight is no greater than that of the spanning tree. Deleting cycles and pruning leaves outside U U U yields a 2-approximate Steiner tree.
Proof. Doubling the edges of an optimal Steiner tree for U U U in Q Q Q yields an Eulerian tour of weight 2 OPT Q ( U ) 2\operatorname{OPT}_Q(U) 2 OPT Q ( U ) visiting all terminals in U U U . Shortcutting this tour between consecutive first visits to terminals in U U U gives a spanning path of K Q ( U ) K_Q(U) K Q ( U ) of weight at most 2 OPT Q ( U ) 2\operatorname{OPT}_Q(U) 2 OPT Q ( U ) by the triangle inequality, so mst ( K Q ( U ) ) ≤ 2 OPT Q ( U ) \operatorname{mst}(K_Q(U)) \le2\operatorname{OPT}_Q(U) mst ( K Q ( U )) ≤ 2 OPT Q ( U ) . Expanding the edges of any spanning tree of K Q ( U ) K_Q(U) K Q ( U ) into shortest paths in Q Q Q and taking their union connects U U U while counting shared edges only once, and removing cycles and non-U U U leaves preserves connectivity on U U U without increasing weight.
Nearest-terminal forest. To avoid constructing the Θ ( ∣ U ∣ 2 ) \Theta(|U|^2) Θ ( ∣ U ∣ 2 ) -edge metric clique K Q ( U ) K_Q(U) K Q ( U ) explicitly, Mehlhorn [Meh88] partitions V ( Q ) V(Q) V ( Q ) into Voronoi regions around the terminals. Given a connected graph Q Q Q with N N N vertices, M M M edges, and positive edge weights, and a nonempty terminal set U ⊆ V ( Q ) U \subseteq V(Q) U ⊆ V ( Q ) , a single multi-source Dijkstra computation initialized with all terminals in U U U (with consistent tie-breaking) runs in O ( ( M + N ) log N ) O((M+N)\log N) O (( M + N ) log N ) time and assigns each vertex x ∈ V ( Q ) x \in V(Q) x ∈ V ( Q ) a nearest terminal a ( x ) ∈ U a(x) \in U a ( x ) ∈ U , called its owner , at distance
δ ( x ) = d Q ( a ( x ) , x ) = min u ∈ U d Q ( u , x ) . \delta(x) = d_Q(a(x),x) = \min_{u\in U} d_Q(u,x). δ ( x ) = d Q ( a ( x ) , x ) = u ∈ U min d Q ( u , x ) .
The shortest-path tree edges recorded by Dijkstra form a rooted forest—called the owner forest —in which each terminal u ∈ U u \in U u ∈ U is the root of a tree spanning its owned region { x ∈ V ( Q ) : a ( x ) = u } \{x \in V(Q): a(x)=u\} { x ∈ V ( Q ) : a ( x ) = u } .
Cross-region edges and metric MST construction. Given the partition of V ( Q ) V(Q) V ( Q ) into terminal owner regions, we can replace the dense metric closure K Q ( U ) K_Q(U) K Q ( U ) by a sparse graph on U U U generated only by edges that cross between different regions. Call an edge x y xy x y a cross-region edge if its endpoints belong to different owner regions, namely, a ( x ) ≠ a ( y ) a(x) \ne a(y) a ( x ) = a ( y ) . Conceptually, represent each region by a supernode identified with its terminal root. Each cross-region edge x y xy x y gives a candidate edge between terminals a ( x ) a(x) a ( x ) and a ( y ) a(y) a ( y ) with weight
b x y = δ ( x ) + w ( x y ) + δ ( y ) . (2) b_{xy} = \delta(x) + w(xy) + \delta(y). \tag*{(2)} b x y = δ ( x ) + w ( x y ) + δ ( y ) . (2)
This weight is the length of a realizable route in Q Q Q that follows the owner tree from a ( x ) a(x) a ( x ) to x x x , crosses x y xy x y , and follows the other owner tree from y y y to a ( y ) a(y) a ( y ) . Figure 1 illustrates this construction.
Figure 1. A cross-region edge x y xy x y induces a candidate edge between terminals a ( x ) a(x) a ( x ) and a ( y ) a(y) a ( y ) with weight b x y = δ ( x ) + w ( x y ) + δ ( y ) b_{xy} = \delta(x) + w(xy) + \delta(y) b x y = δ ( x ) + w ( x y ) + δ ( y ) . Arrows indicate its route in Q Q Q from a ( x ) a(x) a ( x ) to a ( y ) a(y) a ( y ) ; the dashed curve represents the candidate edge.
Construct the candidate graph C 0 C_0 C 0 by scanning all M M M edges of Q Q Q and discarding those whose endpoints have the same owner. Among all candidate edges crossing the same two regions, retain one candidate edge of minimum weight. The resulting graph C 0 C_0 C 0 is a simple weighted graph on U U U with at most M M M edges.
Lemma 2.7 (Equality of cut minima). For any partition of terminal set U U U into two nonempty groups A A A and U ∖ A U \setminus A U ∖ A , the cheapest edge crossing this cut has the same weight in C 0 C_0 C 0 and in K Q ( U ) K_Q(U) K Q ( U ) .
Proof. Every candidate edge in C 0 C_0 C 0 represents a walk in Q Q Q between its terminal endpoints, so its weight is at least their distance in Q Q Q ; hence the minimum weight crossing ( A , U ∖ A ) (A, U \setminus A) ( A , U ∖ A ) in C 0 C_0 C 0 is at least that in K Q ( U ) K_Q(U) K Q ( U ) . Conversely, let u ∈ A u \in A u ∈ A and v ∈ U ∖ A v \in U \setminus A v ∈ U ∖ A minimize d Q ( u , v ) d_Q(u,v) d Q ( u , v ) , and fix a shortest u u u –v v v path P P P in Q Q Q . Since a ( u ) = u ∈ A a(u) = u \in A a ( u ) = u ∈ A and a ( v ) = v ∈ U ∖ A a(v) = v \in U \setminus A a ( v ) = v ∈ U ∖ A , the path P P P contains an edge x y xy x y with a ( x ) ∈ A a(x) \in A a ( x ) ∈ A and a ( y ) ∈ U ∖ A a(y) \in U \setminus A a ( y ) ∈ U ∖ A . Because δ ( x ) ≤ d Q ( u , x ) \delta(x) \leq d_Q(u,x) δ ( x ) ≤ d Q ( u , x ) and δ ( y ) ≤ d Q ( y , v ) \delta(y) \leq d_Q(y,v) δ ( y ) ≤ d Q ( y , v ) , the induced candidate edge between a ( x ) a(x) a ( x ) and a ( y ) a(y) a ( y ) crosses ( A , U ∖ A ) (A, U \setminus A) ( A , U ∖ A ) with weight
b x y = δ ( x ) + w ( x y ) + δ ( y ) ≤ d Q ( u , x ) + w ( x y ) + d Q ( y , v ) = d Q ( u , v ) , b_{xy} = \delta(x) + w(xy) + \delta(y) \leq d_Q(u,x) + w(xy) + d_Q(y,v) = d_Q(u,v), b x y = δ ( x ) + w ( x y ) + δ ( y ) ≤ d Q ( u , x ) + w ( x y ) + d Q ( y , v ) = d Q ( u , v ) ,
and the lightest parallel candidate edge retained in C 0 C_0 C 0 is no heavier. □ \square □
Because C 0 C_0 C 0 and K Q ( U ) K_Q(U) K Q ( U ) have identical minimum cut weights across every partition of U U U , the cut property of minimum spanning trees implies that an MST of the sparse candidate graph C 0 C_0 C 0 is also an exact MST of K Q ( U ) K_Q(U) K Q ( U ) .
Theorem 2.8 (Mehlhorn terminal-MST construction [Meh88]). An MST T 0 T_0 T 0 of the candidate graph C 0 C_0 C 0 is also an MST of the terminal metric closure K Q ( U ) K_Q(U) K Q ( U ) . Every selected candidate edge has weight equal to the distance in Q Q Q between its terminal endpoints and therefore represents an exact shortest path between them. The entire construction takes O ~ ( M + N ) \widetilde{O}(M + N) O ( M + N ) time and O ( M + N ) O(M + N) O ( M + N ) working space, without explicitly constructing the metric clique.
Proof. Starting from an MST of K Q ( U ) K_Q(U) K Q ( U ) , repeatedly replacing each metric edge by a lightest edge in C 0 C_0 C 0 crossing the induced cut (which has no greater weight by Lemma 2.7 ) produces a spanning tree of C 0 C_0 C 0 of weight at most mst ( K Q ( U ) ) \operatorname{mst}(K_Q(U)) mst ( K Q ( U )) , so mst ( C 0 ) ≤ mst ( K Q ( U ) ) \operatorname{mst}(C_0) \leq\operatorname{mst}(K_Q(U)) mst ( C 0 ) ≤ mst ( K Q ( U )) . Conversely, every edge u v ∈ E ( C 0 ) uv \in E(C_0) uv ∈ E ( C 0 ) corresponds to a walk in Q Q Q of weight w C 0 ( u v ) ≥ d Q ( u , v ) w_{C_0}(uv) \geq d_Q(u,v) w C 0 ( uv ) ≥ d Q ( u , v ) , so for an MST T 0 T_0 T 0 of C 0 C_0 C 0 ,
mst ( K Q ( U ) ) ≤ ∑ u v ∈ E ( T 0 ) d Q ( u , v ) ≤ ∑ u v ∈ E ( T 0 ) w C 0 ( u v ) = mst ( C 0 ) ≤ mst ( K Q ( U ) ) . \operatorname{mst}(K_Q(U)) \leq\sum_{uv \in E(T_0)} d_Q(u,v) \leq\sum_{uv \in E(T_0)} w_{C_0}(uv) = \operatorname{mst}(C_0) \leq\operatorname{mst}(K_Q(U)). mst ( K Q ( U )) ≤ uv ∈ E ( T 0 ) ∑ d Q ( u , v ) ≤ uv ∈ E ( T 0 ) ∑ w C 0 ( uv ) = mst ( C 0 ) ≤ mst ( K Q ( U )) . Equality holds throughout, so T 0 T_0 T 0 is an MST of K Q ( U ) K_Q(U) K Q ( U ) and w C 0 ( u v ) = d Q ( u , v ) w_{C_0}(uv) = d_Q(u,v) w C 0 ( uv ) = d Q ( u , v ) for every u v ∈ E ( T 0 ) uv \in E(T_0) uv ∈ E ( T 0 ) . Finally, running multi-source Dijkstra from U U U , scanning the M M M edges of Q Q Q to build and deduplicate C 0 C_0 C 0 , and computing an MST of C 0 C_0 C 0 (on ∣ U ∣ ≤ N |U| \leq N ∣ U ∣ ≤ N vertices and at most M M M edges) each take O ~ ( M + N ) \widetilde{O}(M + N) O ( M + N ) time and O ( M + N ) O(M + N) O ( M + N ) space. □ \square □
Coherent tree expansion. Each edge of the terminal-metric MST T 0 T_0 T 0 represents a shortest path in Q Q Q between two terminals, and several such paths may share edges inside the owner forest. In the dynamic setting, maintaining these paths separately would allow a single edge deletion to invalidate many routes of T 0 T_0 T 0 simultaneously. Instead, we expand T 0 T_0 T 0 along the rooted owner forest and deduplicate shared predecessor edges to obtain a single tree P 0 ⊆ Q P_0 \subseteq Q P 0 ⊆ Q spanning U U U , localizing the effect of any edge deletion to a single edge of P 0 P_0 P 0 .
Lemma 2.9 (Coherent expansion guarantee). The union P 0 P_0 P 0 obtained by expanding the terminal-metric MST T 0 T_0 T 0 using the owner forest and the corresponding cross-region edges is a tree in Q Q Q containing the terminal set U U U , and
w ( P 0 ) ≤ w ( T 0 ) ≤ 2 OPT Q ( U ) . w(P_0) \leq w(T_0) \leq2\operatorname{OPT}_{Q}(U). w ( P 0 ) ≤ w ( T 0 ) ≤ 2 OPT Q ( U ) . Given the owner forest and these cross-region edges, P 0 P_0 P 0 can be constructed in O ( N ) O(N) O ( N ) time.
Proof. Within each owner region, the union of the owner-forest paths from the endpoints of selected cross-region edges to their terminal root forms a subtree of that region’s owner tree. Contracting each such subtree to its terminal root reduces P 0 P_0 P 0 to the tree T 0 T_0 T 0 , so P 0 P_0 P 0 is connected and acyclic, and thus a tree containing U U U . Counting each shared edge once gives w ( P 0 ) ≤ w ( T 0 ) ≤ 2 OPT Q ( U ) w(P_0) \leq w(T_0) \leq2\operatorname{OPT}_{Q}(U) w ( P 0 ) ≤ w ( T 0 ) ≤ 2 OPT Q ( U ) by Lemma 2.6 . To construct P 0 P_0 P 0 in O ( N ) O(N) O ( N ) time, we walk up the owner forest from both endpoints of each of the ∣ U ∣ − 1 \lvert U\rvert- 1 ∣ U ∣ − 1 cross-region edges of T 0 T_0 T 0 , marking visited vertices and stopping each walk upon reaching a terminal root or an already marked vertex so that each of the at most N N N owner-forest edges is traversed at most once. □
MST under graph augmentation. During an update phase, our algorithms augment the frozen terminal metric closure K S ( R ) K_S(R) K S ( R ) with a small set of edges. Rather than maintaining the dense graph K S ( R ) ∪ C K_S(R) \cup C K S ( R ) ∪ C , the following general MST sparsification lemma shows that replacing K S ( R ) K_S(R) K S ( R ) by its precomputed MST T 0 T_0 T 0 preserves the minimum spanning tree weight exactly.
Lemma 2.10 (MST under graph augmentation). Let K K K be a connected weighted graph, and let T 0 T_0 T 0 be an MST of K K K . Augment K K K by adding a set C C C of weighted edges, either connecting existing vertices of K K K or introducing new vertices, such that K ∪ C K \cup C K ∪ C is connected. Then
mst ( K ∪ C ) = mst ( T 0 ∪ C ) . \operatorname{mst}(K \cup C) = \operatorname{mst}(T_0 \cup C). mst ( K ∪ C ) = mst ( T 0 ∪ C ) . Parallel edges are allowed and retained as distinct edges in K ∪ C K \cup C K ∪ C and T 0 ∪ C T_0 \cup C T 0 ∪ C .
Proof. Since T 0 ∪ C ⊂ K ∪ C T_0 \cup C \subset K \cup C T 0 ∪ C ⊂ K ∪ C , we have mst ( K ∪ C ) ≤ mst ( T 0 ∪ C ) \operatorname{mst}(K \cup C) \leq\operatorname{mst}(T_0 \cup C) mst ( K ∪ C ) ≤ mst ( T 0 ∪ C ) . Conversely, let T T T be an MST of K ∪ C K \cup C K ∪ C . For any edge e = u v ∈ E ( T ) ∩ E ( K ∖ T 0 ) e = uv \in E(T) \cap E(K \setminus T_0) e = uv ∈ E ( T ) ∩ E ( K ∖ T 0 ) , the cycle property of the MST T 0 T_0 T 0 of K K K ensures that every edge on the unique u u u -v v v path in T 0 T_0 T 0 has weight at most w ( e ) w(e) w ( e ) . Removing e e e splits T T T into two components, and at least one edge f f f on the u u u -v v v path in T 0 T_0 T 0 crosses this cut; replacing e e e by f f f yields a spanning tree of K ∪ C K \cup C K ∪ C with weight at most w ( T ) w(T) w ( T ) and one fewer edge from K ∖ T 0 K \setminus T_0 K ∖ T 0 . Repeating this exchange eliminates all edges of K ∖ T 0 K \setminus T_0 K ∖ T 0 , producing a spanning tree of T 0 ∪ C T_0 \cup C T 0 ∪ C of weight at most w ( T ) = mst ( K ∪ C ) w(T) = \operatorname{mst}(K \cup C) w ( T ) = mst ( K ∪ C ) . □
Insertion-only Algorithm
We introduce our framework in a simpler form for insertion-only updates. Our approach is to divide the update sequence into phases of B B B insertions and combine two components that together help us avoid recomputing terminal distances:
Frozen structures , computed once at the beginning of each phase on top of the dynamic spanner S t S_t S t , provide graph-wide routing information, including a baseline terminal-metric MST T 0 T_0 T 0 , nearest-terminal owners a ( x ) ∈ R a(x) \in R a ( x ) ∈ R , and approximate all-pairs distances in S S S .
Steiner augmentation structures , updated after each insertion on the at most 2 B 2B 2 B endpoints touched by the current phase, capture information associated with newly inserted edges, such as routes that use new edges and certain augmentations of T 0 T_0 T 0 .
Because no edges are deleted in the insertion-only model, all phase-start routes in S S S remain valid throughout the phase; new insertions can only create cheaper connections between terminal owner regions, which we incorporate into T 0 T_0 T 0 via the MST augmentation property (Lemma 2.10 ). We describe the algorithm below and defer full implementation details and proofs to Appendix § 6 .
Frozen structures. In the background, we maintain the dynamic spanner S t ⊆ G t S_t \subseteq G_t S t ⊆ G t of Theorem 2.1 with stretch σ = ( 2 s − 1 ) ( 1 + δ ) \sigma= (2s-1)(1+\delta) σ = ( 2 s − 1 ) ( 1 + δ ) (for a fixed integer s ≥ 2 s \ge2 s ≥ 2 and constant 0 < δ < 1 0 < \delta< 1 0 < δ < 1 ) and expected size O ~ ( s n 1 + 1 / s ) \widetilde{O}(sn^{1+1/s}) O ( s n 1 + 1/ s ) . At the beginning of each phase, we copy the current spanner into a frozen snapshot S S S and compute two static structures on S S S :
We run Mehlhorn’s construction (Theorem 2.8) on ( S , R ) (S, R) ( S , R ) to obtain a terminal-metric MST T 0 T_0 T 0 of K S ( R ) K_S(R) K S ( R ) , each vertex’s nearest terminal owner a ( x ) ∈ R a(x) \in R a ( x ) ∈ R , its owner distance δ ( x ) = d S ( a ( x ) , x ) \delta(x) = d_S(a(x), x) δ ( x ) = d S ( a ( x ) , x ) , and the rooted owner forest in S S S .
We build the Thorup–Zwick path-reporting distance oracle (Theorem 2.3) on S S S with stretch A = 2 r − 1 A = 2r - 1 A = 2 r − 1 (for a fixed integer r ≥ 2 r \ge2 r ≥ 2 ), which answers queries with distance estimates d S ( x , y ) ≤ d ^ S ( x , y ) ≤ A d S ( x , y ) d_S(x,y) \le\widehat{d}_S(x,y) \le A d_S(x,y) d S ( x , y ) ≤ d S ( x , y ) ≤ A d S ( x , y ) and realizing walks in S S S .
Steiner augmentation structures. Let F F F denote the set of edges inserted so far in the current phase and let X X X be the set of their endpoints, so ∣ F ∣ ≤ B |F| \le B ∣ F ∣ ≤ B and ∣ X ∣ ≤ 2 B |X| \le2B ∣ X ∣ ≤ 2 B . Because any route in S ∪ F S \cup F S ∪ F that improves upon S S S must traverse at least one edge of F F F , we maintain a weighted multigraph L F L_F L F on the endpoint set X X X with two types of edges:
every newly inserted edge e ∈ F e \in F e ∈ F with its actual weight w ( e ) w(e) w ( e ) ; and
for every pair of distinct vertices x , y ∈ X x,y \in X x , y ∈ X , a virtual edge of weight d ^ S ( x , y ) \widehat{d}_S(x,y) d S ( x , y ) queried from the phase-start distance oracle on S S S .
As edges are inserted into F F F , we maintain exact all-pairs shortest-path distances D F ( x , y ) = d L F ( x , y ) D_F(x,y) = d_{L_F}(x,y) D F ( x , y ) = d L F ( x , y ) and a next-hop matrix on L F L_F L F in O ( ∣ X ∣ 2 ) = O ( B 2 ) O(|X|^2) = O(B^2) O ( ∣ X ∣ 2 ) = O ( B 2 ) time per insertion. Thus, D F ( x , y ) D_F(x,y) D F ( x , y ) records the cheapest walk between x x x and y y y that combines newly inserted edges in F F F with oracle paths in S S S .
Maintaining the augmented terminal MST. To translate shortest paths in L F L_F L F into connections between terminals in R R R , we route each endpoint x ∈ X x \in X x ∈ X to its frozen terminal owner a ( x ) ∈ R a(x) \in R a ( x ) ∈ R along the owner forest in S S S . Specifically, after updating D F D_F D F on an insertion, for every pair x , y ∈ X x,y \in X x , y ∈ X with a ( x ) ≠ a ( y ) a(x) \ne a(y) a ( x ) = a ( y ) , we create or update a candidate edge between terminals a ( x ) a(x) a ( x ) and a ( y ) a(y) a ( y ) of weight
c x y = δ ( x ) + D F ( x , y ) + δ ( y ) , (3) c_{xy} = \delta(x) + D_F(x,y) + \delta(y), \tag*{(3)} c x y = δ ( x ) + D F ( x , y ) + δ ( y ) , (3)
which never increases during the phase because δ ( ⋅ ) \delta(\cdot) δ ( ⋅ ) is fixed and insertions can only decrease D F ( x , y ) D_F(x,y) D F ( x , y ) . Each candidate edge a ( x ) a ( y ) a(x)a(y) a ( x ) a ( y ) represents a walk in the current graph formed by concatenating the owner-forest path from a ( x ) a(x) a ( x ) to x x x , the shortest path in L F L_F L F from x x x to y y y (with virtual edges expanded via the path-reporting oracle on S S S ), and the owner-forest path from y y y to a ( y ) a(y) a ( y ) . Letting C F C_F C F denote the set of these O ( B 2 ) O(B^2) O ( B 2 ) candidate edges on R R R , we maintain a minimum spanning tree M \mathcal{M} M of the augmented graph T 0 ∪ C F T_0 \cup C_F T 0 ∪ C F . By the MST augmentation property,
mst ( T 0 ∪ C F ) = mst ( K S ( R ) ∪ C F ) , (4) \operatorname{mst}(T_0 \cup C_F) = \operatorname{mst}(K_S(R) \cup C_F), \tag*{(4)} mst ( T 0 ∪ C F ) = mst ( K S ( R ) ∪ C F ) , (4)
so maintaining an MST of T 0 ∪ C F T_0 \cup C_F T 0 ∪ C F achieves the exact same weight as maintaining an MST of the full terminal metric K S ( R ) K_S(R) K S ( R ) augmented with C F C_F C F . Since candidate weights only decrease during a phase, we can maintain M \mathcal{M} M dynamically in O ( log n ) O(\log n) O ( log n ) time per candidate update using a link–cut tree [ST81], taking O ( B 2 log n ) O(B^2 \log n) O ( B 2 log n ) time per insertion. When an explicit Steiner tree is requested, we coherently expand the owner-forest routes of M \mathcal{M} M in S S S , extract a spanning forest of the L F L_F L F -paths for the O ( B ) O(B) O ( B ) selected candidate edges and materialize its virtual edges via the path-reporting oracle, and finally delete cycles and prune non-terminal leaves.
After B B B insertions occur, we start a new phase and rebuild the frozen structures on the current spanner. We also reset F F F , X X X , and C F C_F C F . Balancing this periodic rebuild cost against the per-insertion update cost yields our amortized update time. In particular, choosing B = ⌈ n ( 1 + 1 / s + 1 / r ) / 3 ⌉ B = \left\lceil n^{(1+1/s+1/r)/3} \right\rceil B = ⌈ n ( 1 + 1/ s + 1/ r ) /3 ⌉ gives the guarantee stated in Theorem 1.2 .
The fully dynamic algorithm in § 4 retains the same framework, combining frozen structures with within-phase Steiner augmentation structures and mapping endpoints of newly inserted edges to their frozen terminal owners a ( u ) , a ( v ) ∈ R a(u), a(v) \in R a ( u ) , a ( v ) ∈ R . However, deleting an edge may invalidate many routes represented by the terminal MST T 0 T_0 T 0 . To localize this impact, we will expand T 0 T_0 T 0 into a tree P 0 P_0 P 0 , where a deletion removes only the corresponding edge, and represent both newly inserted edges (via their owners a ( u ) , a ( v ) a(u), a(v) a ( u ) , a ( v ) ) and deleted edges of P 0 P_0 P 0 (via their endpoints u , v u,v u , v ) by zero-weight spokes to an artificial hub h h h . Rather than maintaining the auxiliary multigraph L F L_F L F and candidate edges C F C_F C F , a top-tree dynamic program will select portions of P 0 P_0 P 0 to retain. A dynamic distance sparsifier estimates the reconnection cost, while Mehlhorn’s construction on the current spanner reconnects these portions when an explicit solution is requested.
Fully Dynamic Algorithm
This section is devoted to our main result, a fully dynamic algorithm for the Steiner tree problem that simultaneously achieves sublinear-in-n n n update time and a constant factor approximation. Our algorithm builds on the dynamic spanner of Chuzhoy and Parter [CP25] (cf. Theorem 2.2) and the HLS distance sparsifier (cf. Theorem 2.5) to maintain a sparse tree spanning the terminals, while dynamically reconnecting its surviving pieces as edges are inserted and deleted. We present the overall algorithm in § 4.1 , followed by the details of its two core components: the maintenance of a minimum Steiner tree on a certain augmented tree in § 4.2 , and the component repair procedure in § 4.3 . We then establish the approximation guarantee in § 5 and conclude with the update-time, reporting, and space analysis in § 5.3 .
Algorithm
We divide the update sequence into phases of B B B updates each. Let G o G^o G o denote the graph at the start of a phase; objects described as frozen are computed from G o G^o G o at the phase boundary and remain fixed throughout the phase, whereas the current graph G t G_t G t continues to evolve. Across all phases, our algorithm maintains two persistent data structures on the current graph G t G_t G t : CP’s deterministic dynamic σ \sigma σ -spanner S t ⊆ G t S_t \subseteq G_t S t ⊆ G t with σ = σ V \sigma= \sigma_V σ = σ V and an explicit HLS distance sparsifier H t H_t H t on a designated vertex set U t ⊆ V U_t \subseteq V U t ⊆ V containing a fixed root terminal r 0 ∈ R r_0 \in R r 0 ∈ R . To respect the integer-weight requirements of Theorems 2.2 and 2.5 , all internal structures operate on the rounded integer weights w ^ ( e ) = ⌈ w ( e ) / ε ⌉ \widehat{w}(e) = \lceil w(e)/\varepsilon\rceil w ( e ) = ⌈ w ( e ) / ε ⌉ from (1); we write w w w for w ^ \widehat{w} w throughout to ease notation. We now describe how the algorithm builds its frozen structures at the start of a phase, maintains its Steiner augmentation structures, and reports an explicit Steiner tree upon query.
Frozen structures. At the beginning of each phase, we take a frozen copy S ⊆ G ∘ S \subseteq G^\circ S ⊆ G ∘ of the current dynamic spanner S t S_t S t and construct the following structures in two steps:
Terminal-metric MST and owner forest. We run Mehlhorn’s construction (Theorem 2.8) on S S S with terminal set R R R to obtain each vertex’s nearest terminal owner a ( x ) ∈ R a(x) \in R a ( x ) ∈ R , its owner distance δ ( x ) = d S ( a ( x ) , x ) \delta(x) = d_S(a(x), x) δ ( x ) = d S ( a ( x ) , x ) , the rooted owner forest, and an MST T 0 T_0 T 0 of K S ( R ) K_S(R) K S ( R ) .
Coherent tree expansion. Because a single edge deletion could invalidate many routes of T 0 T_0 T 0 simultaneously, we apply Lemma 2.9 to expand T 0 T_0 T 0 along the owner forest into a single tree P 0 ⊆ S P_0 \subseteq S P 0 ⊆ S spanning R R R , retaining each shared edge only once.
Steiner augmentation structures. To track updates during a phase and decide which surviving pieces of P 0 P_0 P 0 to retain, we augment P 0 P_0 P 0 at the start of the phase with an artificial vertex h h h , called hub , and a zero-weight artificial edge z h zh z h , called a spoke , for every vertex z ∈ V ( P 0 ) z \in V(P_0) z ∈ V ( P 0 ) . Each edge of P 0 P_0 P 0 and each spoke may be enabled or disabled; we denote by J t J_t J t the subgraph of enabled edges at time t t t , and call a vertex z z z whose spoke z h zh z h is enabled an active vertex (or an active terminal when z ∈ R z \in R z ∈ R ). At the start of a phase, all edges of P 0 P_0 P 0 are enabled and all spokes are disabled. As updates arrive during the phase, we update J t J_t J t as follows:
Insertion handling. Inserting an edge u v uv uv enables the spokes a ( u ) h a(u)h a ( u ) h and a ( v ) h a(v)h a ( v ) h at the endpoints’ frozen terminal owners a ( u ) , a ( v ) ∈ R a(u), a(v) \in R a ( u ) , a ( v ) ∈ R , providing a zero-cost connection through h h h that allows the algorithm to omit expensive old routes in P 0 P_0 P 0 .
Deletion handling. Deleting an edge u v ∈ E ( P 0 ) uv \in E(P_0) uv ∈ E ( P 0 ) disables u v uv uv in P 0 P_0 P 0 and enables the spokes u h uh u h and v h vh v h at its endpoints u , v ∈ V ( P 0 ) u, v \in V(P_0) u , v ∈ V ( P 0 ) (which need not be terminals), providing a zero-cost bridge across the resulting gap in P 0 P_0 P 0 . Deleting an edge outside E ( P 0 ) E(P_0) E ( P 0 ) leaves J t J_t J t unchanged.
Once enabled, a spoke remains enabled until the phase ends. Letting A t ⊆ R A_t \subseteq R A t ⊆ R denote the set of active terminals , namely the frozen owners of all endpoints of edges inserted during the phase, and D t ⊆ E ( P 0 ) D_t \subseteq E(P_0) D t ⊆ E ( P 0 ) denote the edges of P 0 P_0 P 0 deleted during the phase, the set of active vertices at time t t t is
Z t = A t ∪ end ( D t ) , (5) Z_t = A_t \cup\operatorname{end}(D_t), \tag*{(5)} Z t = A t ∪ end ( D t ) , (5)
where end ( D t ) \operatorname{end}(D_t) end ( D t ) consists of the endpoints of all edges in D t D_t D t ; the resulting auxiliary graph is
J t = ( P 0 − D t ) ∪ { z h : z ∈ Z t } , w ( z h ) = 0. (6) J_t = (P_0 - D_t) \cup\{zh : z \in Z_t\}, \qquad w(zh) = 0. \tag*{(6)} J t = ( P 0 − D t ) ∪ { z h : z ∈ Z t } , w ( z h ) = 0. (6)
Note that sets A t A_t A t , D t D_t D t , and Z t ⊆ V ( P 0 ) Z_t \subseteq V(P_0) Z t ⊆ V ( P 0 ) only grow within a phase and each has size O ( B ) O(B) O ( B ) .
Reconnecting surviving subtrees. After updating J t J_t J t and forwarding the graph update to S t S_t S t and H t H_t H t , our algorithm maintains its implicit Steiner tree in three steps:
Maintaining an exact Steiner tree on J t J_t J t (§ 4.2 ). Using dynamic programming over a fixed top-tree hierarchy on P 0 P_0 P 0 , we maintain a minimum Steiner tree T t J T_t^J T t J connecting R R R in J t J_t J t that lexicographically minimizes
( weight , number of spokes , number of edges ) . (\text{weight},\ \text{number of spokes},\ \text{number of edges}). ( weight , number of spokes , number of edges ) .
Removing the artificial vertex h h h and its selected spokes from T t J T_t^J T t J leaves a surviving forest F t = T t J − h ⊆ P 0 − D t F_t = T_t^J - h \subseteq P_0 - D_t F t = T t J − h ⊆ P 0 − D t . When T t J T_t^J T t J uses h h h , lexicographic optimality ensures that each component of F t F_t F t contains a terminal in R R R and a unique selected spoke to h h h (Lemma 4.1 ). Collecting the endpoints in P 0 P_0 P 0 of these selected spokes gives a set Q t ⊆ Z t ∪ { r 0 } Q_t \subseteq Z_t \cup\{r_0\} Q t ⊆ Z t ∪ { r 0 } of component representatives of size O ( B ) O(B) O ( B ) (with Q t = { r 0 } Q_t = \{r_0\} Q t = { r 0 } when h h h is unused). (2) Estimating reconnection cost via distance sparsifier (§ 4.3 ). Because each component of F t F_t F t connects its terminals to its representative in Q t Q_t Q t , reconnecting Q t Q_t Q t in G t G_t G t suffices to connect R R R . Since Q t Q_t Q t may change substantially after a single update, we maintain the HLS distance sparsifier H t H_t H t on the monotonically growing superset U t = Z t ∪ { r 0 } U_t = Z_t \cup\{r_0\} U t = Z t ∪ { r 0 } , inserting the O ( 1 ) O(1) O ( 1 ) newly active vertices per update and resetting U t U_t U t to { r 0 } \{r_0\} { r 0 } at phase boundaries. We run Mehlhorn’s construction (Theorem 2.8) on H t H_t H t with terminal set Q t Q_t Q t to compute an MST M H M_H M H of K H t ( Q t ) K_{H_t}(Q_t) K H t ( Q t ) , whose scaled weight σ w K H t ( Q t ) ( M H ) \sigma w_{K_{H_t}(Q_t)}(M_H) σ w K H t ( Q t ) ( M H ) upper-bounds the cost of reconnecting Q t Q_t Q t in S t S_t S t .
(3) Implicit representation and tree reporting. The maintained implicit solution consists of the dynamic-programming backpointers on the top tree (encoding F t F_t F t and Q t Q_t Q t ) together with the scalar upper-bound cost estimate c t = w ( F t ) + σ w K H t ( Q t ) ( M H ) c_t = w(F_t) + \sigma w_{K_{H_t}(Q_t)}(M_H) c t = w ( F t ) + σ w K H t ( Q t ) ( M H ) combining the top-tree root weight w ( F t ) w(F_t) w ( F t ) with the scaled sparsifier MST weight. When an explicit Steiner tree is requested, we follow the backpointers to recover F t F_t F t , run Mehlhorn’s construction (Theorem 2.8) and coherent tree expansion (Lemma 2.9 ) on the current spanner S t S_t S t with terminal set Q t Q_t Q t to obtain a tree A S ⊆ S t A_S \subseteq S_t A S ⊆ S t connecting Q t Q_t Q t , and take the union F t ∪ A S F_t \cup A_S F t ∪ A S , removing cycles and pruning nonterminal leaves.
Algorithm Algorithm 1 summarizes initialization, reconstruction, update, and materialization procedures.
Minimum Steiner Tree Maintenance on Hub-Augmented Tree
In this section, we describe how to dynamically maintain a minimum Steiner tree T t J T_t^J T t J connecting R R R in J t = ( P 0 − D t ) ∪ { z h : z ∈ Z t } J_t = (P_0 - D_t) \cup\{z_h : z \in Z_t\} J t = ( P 0 − D t ) ∪ { z h : z ∈ Z t } . The graph J t J_t J t has a special tree-plus-star structure: all of its non-spoke edges belong to the fixed tree P 0 P_0 P 0 , and every other edge is a zero-weight spoke incident to the hub h h h . This structure helps us maintain a Steiner tree of minimum cost in O ( log n ) O(\log n) O ( log n ) time per update via dynamic programming. We first give a static algorithm for finding a minimum Steiner tree in J t J_t J t , and then explain how to maintain this optimum dynamically.
Among all Steiner trees connecting R R R in J t J_t J t , we minimize the lexicographic triple
Λ ( Y ) = ( w ( Y ) , number of selected spokes , number of selected edges ) . (7) \Lambda(Y) = (w(Y),\ \text{number of selected spokes},\ \text{number of selected edges}). \tag*{(7)} Λ ( Y ) = ( w ( Y ) , number of selected spokes , number of selected edges ) . (7)
The second coordinate rules out unnecessary free hub spokes, while the third prefers fewer edges. Removing the hub h h h and its incident spokes from T t J T_t^J T t J yields the surviving forest
F t = T t J − h . F_t = T_t^J - h. F t = T t J − h .
If h h h is used in T t J T_t^J T t J , we define the representative set Q t Q_t Q t to consist of the endpoints in P 0 P_0 P 0 of the selected spokes; if h h h is unused, we set Q t = { r 0 } Q_t = \{r_0\} Q t = { r 0 } . Minimizing (7) guarantees that each component of F t F_t F t spans at least one terminal and has a unique representative:
Lemma 4.1 (One representative per retained component). Every component of F t F_t F t contains at least one original terminal and exactly one representative. If the hub is used, F t F_t F t has at least two components, each connected to the hub by exactly one selected spoke. If the hub is unused, F t F_t F t is connected and Q t = { r 0 } Q_t = \{r_0\} Q t = { r 0 } .
Proof. Every connected component of F t F_t F t must contain a terminal in R R R : otherwise, pruning that component and its incident spokes from the tree T t J T_t^J T t J would preserve connectivity on R R R while strictly improving Λ ( T t J ) \Lambda(T_t^J) Λ ( T t J ) (decreasing either weight or spoke count), contradicting optimality. If F t F_t F t has multiple components, each must be incident to at least one spoke in T t J T_t^J T t J to reach the others through h h h , and at most one spoke because two spokes into the same component of F t F_t F t would create a cycle
Algorithm 1 Fully Dynamic Steiner Tree Algorithm
procedure Initialize (G 0 , R G_0, R G 0 , R )
Set rounded weights w ^ ( e ) ← ⌈ w ( e ) / ε ⌉ \widehat{w}(e) \leftarrow\lceil w(e)/\varepsilon\rceil w ( e ) ← ⌈ w ( e ) / ε ⌉ for all e ∈ E 0 e \in E_0 e ∈ E 0 . Fix a root terminal r 0 ∈ R r_0 \in R r 0 ∈ R and initialize the deterministic dynamic σ \sigma σ -spanner S t S_t S t (Theorem 2.2 ) and HLS sparsifier H t H_t H t with designated set U t ← { r 0 } U_t \leftarrow\{r_0\} U t ← { r 0 } (Theorem 2.5 ) on G 0 G_0 G 0 (under w ^ \widehat{w} w ).
Call StartPhase ().
procedure StartPhase () ▷ invoked at initialization and every B B B updates
Delete each z ∈ U t ∖ { r 0 } z \in U_t \setminus\{r_0\} z ∈ U t ∖ { r 0 } from the HLS sparsifier H t H_t H t to reset the designated set to U t ← { r 0 } U_t \leftarrow\{r_0\} U t ← { r 0 } , and set the active-vertex set to Z t ← ∅ Z_t \leftarrow\varnothing Z t ← ∅ .
Copy S t S_t S t into a frozen snapshot S ⊆ G ∘ S \subseteq G^\circ S ⊆ G ∘ and run Mehlhorn’s construction (Theorem 2.8 ) on ( S , R ) (S,R) ( S , R ) to obtain terminal owners a ( x ) a(x) a ( x ) , the owner forest, and an MST T 0 T_0 T 0 of K S ( R ) K_S(R) K S ( R ) .
Expand T 0 T_0 T 0 along the owner forest into the tree P 0 ⊆ S P_0 \subseteq S P 0 ⊆ S (Lemma 2.9 ).
Initialize the top-tree data structure (§ 4.2 ) on J t = P 0 J_t = P_0 J t = P 0 under w ^ \widehat{w} w (all P 0 P_0 P 0 edges enabled, all spokes disabled), and set Q t ← { r 0 } Q_t \leftarrow\{r_0\} Q t ← { r 0 } and c t ← w ^ ( P 0 ) c_t \leftarrow\widehat{w}(P_0) c t ← w ( P 0 ) .
procedure Update (op, u v uv uv , w w w ) ▷ see Remark 4.14 for weight changes
If op = insert, set w ^ ( u v ) ← ⌈ w / ε ⌉ \widehat{w}(uv) \leftarrow\lceil w/\varepsilon\rceil w ( uv ) ← ⌈ w / ε ⌉ . Forward the update to G t G_t G t , S t S_t S t , and H t H_t H t .
If u v uv uv is inserted: enable spokes a ( u ) h , a ( v ) h a(u)h,a(v)h a ( u ) h , a ( v ) h in J t J_t J t ; for each z ∈ { a ( u ) , a ( v ) } ∖ U t z \in\{a(u),a(v)\} \setminus U_t z ∈ { a ( u ) , a ( v )} ∖ U t , insert z z z into the designated set U t U_t U t of H t H_t H t ; and add a ( u ) , a ( v ) a(u),a(v) a ( u ) , a ( v ) to Z t Z_t Z t .
If u v ∈ E ( P 0 ) uv \in E(P_0) uv ∈ E ( P 0 ) is deleted: disable u v uv uv and enable spokes u h , v h uh,vh u h , v h in J t J_t J t ; for each z ∈ { u , v } ∖ U t z \in\{u,v\} \setminus U_t z ∈ { u , v } ∖ U t , insert z z z into the designated set U t U_t U t of H t H_t H t ; and add u , v u,v u , v to Z t Z_t Z t .
Select surviving forest (§ 4.2 ): Update the top-tree DP on J t J_t J t to maintain the optimal tree T t J T_t^J T t J and extract the representatives Q t Q_t Q t of F t = T t J − h F_t = T_t^J - h F t = T t J − h .
Reconnect components (§ 4.3 ): Run Mehlhorn’s construction on ( H t , Q t ) (H_t,Q_t) ( H t , Q t ) to compute an MST M H M_H M H of K H t ( Q t ) K_{H_t}(Q_t) K H t ( Q t ) and record c t ← w ^ ( F t ) + σ w K H t ( Q t ) ( M H ) c_t \leftarrow\widehat{w}(F_t) + \sigma w_{K_{H_t}(Q_t)}(M_H) c t ← w ( F t ) + σ w K H t ( Q t ) ( M H ) (cost queries return ε c t \varepsilon c_t ε c t ).
procedure Materialize ()
Recover the forest F t ⊆ P 0 F_t \subseteq P_0 F t ⊆ P 0 by following the top-tree DP backpointers.
Run Mehlhorn’s construction (Theorem 2.8 ) on ( S t , Q t ) (S_t,Q_t) ( S t , Q t ) to compute an MST M S M_S M S of K S t ( Q t ) K_{S_t}(Q_t) K S t ( Q t ) , and expand M S M_S M S along its owner forest in S t S_t S t into a tree A S ⊆ S t A_S \subseteq S_t A S ⊆ S t (Lemma 2.9 ).
In F t ∪ A S F_t \cup A_S F t ∪ A S , delete cycles and prune nonterminal leaves to return a Steiner tree for R R R .
through h h h . Finally, if F t F_t F t has a single component, it already connects R R R , so selecting any spoke would increase the spoke count without reducing weight; hence h h h is unused and Q t = { r 0 } Q_t = \{r_0\} Q t = { r 0 } .
In the remainder of this subsection, we show how to compute and maintain T t J T_t^J T t J . We first decompose P 0 P_0 P 0 into a hierarchy of connected subtrees of height O ( log n ) O(\log n) O ( log n ) using a top tree [3 ] , and assign each edge of P 0 P_0 P 0 and hub spoke of J t J_t J t to a unique cluster where the dynamic program chooses whether to include it. Because each cluster interacts with the rest of J t J_t J t through at most two boundary vertices in P 0 P_0 P 0 and the hub h h h , we can summarize all partial solutions within a cluster using a constant-size DP table of 22 states. Finally, we show that each edge or spoke update only recomputes the O ( log n ) O(\log n) O ( log n ) DP tables along a single cluster-to-root path, and that following backpointers from the root extracts the representatives Q t Q_t Q t in O ( ∣ Q t ∣ log n ) O(|Q_t|\log n) O ( ∣ Q t ∣ log n ) time.
A fixed top-tree hierarchy on P 0 P_0 P 0 . To maintain T t J T_t^J T t J under edge and spoke changes, we organize the fixed tree P 0 P_0 P 0 using a top tree [3 ] . This is a balanced binary hierarchy that recursively merges adjacent connected edge sets of P 0 P_0 P 0 into larger pieces. A node of the hierarchy represents a cluster : a connected set of edges of P 0 P_0 P 0 and their endpoints. The leaves represent individual edges of P 0 P_0 P 0 . Two sibling clusters have disjoint edge sets and share exactly one vertex.
To describe how a cluster connects to the rest of P 0 P_0 P 0 , we identify its boundary vertices . A vertex of a cluster C C C is a boundary vertex (written v ∈ ∂ C v \in\partial C v ∈ ∂ C ) if it is incident to an edge of P 0 ∖ C P_0 \setminus C P 0 ∖ C or equals the fixed root terminal r 0 ∈ R r_0 \in R r 0 ∈ R , which we designate as an external boundary vertex [3 ] . Keeping r 0 r_0 r 0 in ∂ C \partial C ∂ C for every cluster containing it (even when no edge of P 0 ∖ C P_0 \setminus C P 0 ∖ C is incident to r 0 r_0 r 0 ) ensures that at the root cluster we have ∂ P 0 = { r 0 } \partial P_0 = \{r_0\} ∂ P 0 = { r 0 } and all terminals in R R R are connected to r 0 r_0 r 0 .
By [3 ] , building the hierarchy on the O ( n ) O(n) O ( n ) edges of P 0 P_0 P 0 and exposing r 0 r_0 r 0 takes O ( n log n ) O(n \log n) O ( n log n ) time and produces O ( n ) O(n) O ( n ) clusters of height O ( log n ) O(\log n) O ( log n ) such that every cluster C C C has ∣ ∂ C ∣ ≤ 2 |\partial C| \le2 ∣ ∂ C ∣ ≤ 2 , as illustrated in Figure 2 . Crucially, we build this hierarchy on all edges of P 0 P_0 P 0 (including disabled ones), and the hub spokes are not part of the hierarchy. Whether an edge or spoke is enabled determines whether it can be selected by our dynamic program, without altering the shape or boundary sets of the clusters; thus, the cluster tree itself remains fixed throughout the phase, and only the clusters’ DP entries change upon updates.
Figure 2. An example top-tree hierarchy on the four-edge path P 0 P_0 P 0 shown below it. Each box lists its edges and boundary set. The exposed terminal r 0 r_0 r 0 remains a boundary at every containing cluster. The vertex b b b becomes internal only at the root merge; d d d is already internal at its singleton leaf. The hub and spokes are absent from this hierarchy.
Assigning each edge and spoke to a unique cluster. As our bottom-up dynamic program moves up the hierarchy, it builds partial Steiner trees by choosing whether to include or omit each enabled edge of J t J_t J t . For edges of P 0 P_0 P 0 , this choice happens at the leaves. Because the hub spokes are not part of the top tree on P 0 P_0 P 0 , however, we must specify at which cluster the dynamic program chooses whether to include each spoke v h v h v h , so that every spoke is considered exactly once before its endpoint v ∈ V ( P 0 ) v \in V(P_0) v ∈ V ( P 0 ) disappears from the cluster boundary. We have
Each edge e ∈ E ( P 0 ) e \in E(P_0) e ∈ E ( P 0 ) is chosen (included or omitted) at its singleton leaf cluster { e } \{e\} { e } .
Each potential spoke v h v h v h with v ≠ r 0 v \ne r_0 v = r 0 is chosen at the unique cluster where v v v first stops being a boundary vertex, i.e., the smallest cluster containing all edges of P 0 P_0 P 0 incident to v v v . Once all edges of P 0 P_0 P 0 incident to v v v lie inside a cluster, v v v will never appear on the boundary of any ancestor cluster. This cluster is either a singleton leaf if deg P 0 ( v ) = 1 \deg_{P_0}(v) = 1 deg P 0 ( v ) = 1 (such as d d d in Figure 2 ) or the merge of two child clusters A A A and B B B sharing v v v once no edge incident to v v v remains outside A ∪ B A \cup B A ∪ B . The root spoke r 0 h r_0h r 0 h is chosen at the root cluster P 0 P_0 P 0 .
During a merge of two sibling clusters, only their single shared vertex can stop being a boundary vertex, so each merge introduces at most one spoke choice (plus r 0 h r_0h r 0 h at the root). For each edge of P 0 P_0 P 0 and spoke, we store a pointer to the cluster where its choice is made, allowing that cluster’s DP table to be located in O ( 1 ) O(1) O ( 1 ) time when the edge or spoke is enabled or disabled.
Cluster states and dynamic-programming transitions. To build a Steiner tree connecting R R R to r 0 r_0 r 0 , the dynamic program maintains partial solutions at each cluster C C C by selecting enabled edges of the cluster and enabled spokes whose decisions are made in that cluster or its descendants. Once all choices inside C C C have been made, vertices inside C C C can connect to the rest of J t J_t J t outside C C C only through the boundary vertices ∂ C \partial C ∂ C (via edges of P 0 P_0 P 0 outside C C C ) or through the hub h h h (via spokes outside C C C ). We therefore call
I C = ∂ C ∪ { h } , ∣ I C ∣ ≤ 3 , I_C = \partial C \cup\{h\}, \qquad|I_C| \le3, I C = ∂ C ∪ { h } , ∣ I C ∣ ≤ 3 ,
the interfaces of C C C . For a partial solution inside C C C to be extendable to a valid Steiner tree of J t J_t J t , it must satisfy two basic conditions:
Connectivity: Every terminal in C C C must be connected to at least one interface in I C I_C I C . Otherwise, since no edge outside C C C can ever touch an internal vertex of C C C , that terminal would be permanently trapped inside C C C with no way to reach r 0 r_0 r 0 . (Because r 0 r_0 r 0 remains in ∂ C \partial C ∂ C for every cluster containing it, any terminal already connected to r 0 r_0 r 0 automatically satisfies this condition.)
Acyclicity: The edges and spokes selected within C C C must contain no cycle.
A feasible partial solution inside C C C interacts with the rest of J t J_t J t as follows. If a component inside C C C contains a terminal, edges outside C C C must eventually connect it to all other terminal-bearing components, and they can reach it through any interface in I C I_C I C belonging to that component; conversely, if two interfaces in I C I_C I C already lie in the same component inside C C C , connecting them again outside C C C would create a cycle.
We therefore encode a partial solution in C C C by partitioning its interfaces I C I_C I C into connected components within C C C and assigning each group a terminal bit b i ∈ { 0 , 1 } b_i \in\{0,1\} b i ∈ { 0 , 1 } equal to 1 if that component in C C C contains a terminal in R R R , and 0 otherwise. For instance, when ∂ C = { u , v } \partial C = \{u,v\} ∂ C = { u , v } , the states
{ u } 1 ∣ { v } 1 ∣ { h } 0 and { u , v } 1 ∣ { h } 0 \{u\}_1 \mid\{v\}_1 \mid\{h\}_0 \qquad\text{and} \qquad\{u,v\}_1 \mid\{h\}_0 { u } 1 ∣ { v } 1 ∣ { h } 0 and { u , v } 1 ∣ { h } 0
express different connectivity needs: in the first state, u u u and v v v lie in separate terminal-bearing components inside C C C , so edges outside C C C must eventually connect both u u u and v v v ; in the second state, u u u and v v v are already joined inside C C C , so connecting through either u u u or v v v suffices to reach all terminals in their shared component. With up to three interfaces u , v , h u,v,h u , v , h , there are at most 22 states:
Table 1 (PDF p. 23).
Each cluster’s DP table stores, for each state, the minimum cost triple (7) over all feasible partial solutions inducing that state (or + ∞ +\infty + ∞ if none exists), together with backpointers to the local edge/spoke choices and child states achieving it. We now describe how to compute these DP tables bottom-up in three stages: initializing singleton leaves, merging sibling clusters, and selecting the final tree at the root.
Singleton leaves. A leaf cluster C = { e } C = \{e\} C = { e } with e = u v e = uv e = uv has at most two edges assigned to it (e e e and, for any endpoint v ∉ ∂ C v \notin\partial C v ∈ / ∂ C , the spoke v h vh v h ), giving at most four enabled subsets (or at most eight if the singleton is also the root and decides r 0 h r_0h r 0 h ). We reject any subset that leaves a terminal endpoint of e e e with no interface in I C I_C I C . For each feasible subset, we record its induced partition and terminal bits on I C I_C I C with cost ( w ( e ) , 0 , 1 ) (w(e), 0, 1) ( w ( e ) , 0 , 1 ) if e e e is selected (and ( 0 , 0 , 0 ) (0, 0, 0) ( 0 , 0 , 0 ) otherwise), plus ( 0 , 1 , 1 ) (0, 1, 1) ( 0 , 1 , 1 ) per selected spoke, keeping the minimum cost and local choices for each state in O ( 1 ) O(1) O ( 1 ) time.
Internal merges. To compute the table of C = A ∪ B C = A \cup B C = A ∪ B from its children A A A and B B B sharing boundary vertex v v v , we enumerate the at most 2 2 × 2 2 × 2 2^2 \times2^2 \times2 2 2 × 2 2 × 2 combinations of finite-cost child states ( s A , s B ) (s_A, s_B) ( s A , s B ) and the local spoke choice at v v v if v ∉ ∂ C v \notin\partial C v ∈ / ∂ C (or × 4 \times4 × 4 at the root to also choose r 0 h r_0h r 0 h ). Using only the recorded interface groups and terminal bits of s A s_A s A and s B s_B s B (without examining internal vertices or paths), we unite the groups connected through v v v , h h h , or v h vh v h , OR their terminal bits, and apply two feasibility checks: (i) Acyclicity: Because A A A and B B B share no edges of P 0 P_0 P 0 or previously chosen spokes and overlap only at v v v and h h h , a cycle arises if and only if v v v and h h h already belong to the same group in both s A s_A s A and s B s_B s B (e.g., { u , v , h } 1 \{u,v,h\}_1 { u , v , h } 1 and { v , w , h } 0 \{v,w,h\}_0 { v , w , h } 0 , where each child provides a distinct v v v –h h h path), or belong to the same group in one child while the spoke v h vh v h is also selected (or, at the root, r 0 r_0 r 0 and h h h already lie in the same merged group when r 0 h r_0h r 0 h is selected). Any such combination is rejected. (ii) No stranded terminals: If v v v becomes internal (v ∉ ∂ C v \notin\partial C v ∈ / ∂ C ), its merged group cannot be reached by any edges outside C C C and must therefore contain at least one surviving interface in I C = ∂ C ∪ { h } I_C = \partial C \cup\{h\} I C = ∂ C ∪ { h } whenever its merged terminal bit is 1 1 1 (rejecting, e.g., { u } 0 ∣ { v } 1 ∣ { h } 0 \{u\}_0 \mid\{v\}_1 \mid\{h\}_0 { u } 0 ∣ { v } 1 ∣ { h } 0 and { v } 0 ∣ { w } 0 ∣ { h } 0 \{v\}_0 \mid\{w\}_0 \mid\{h\}_0 { v } 0 ∣ { w } 0 ∣ { h } 0 when v ∉ ∂ C v \notin\partial C v ∈ / ∂ C and v h vh v h is omitted, since { v } 1 \{v\}_1 { v } 1 loses its last interface). For every combination passing both checks, we project its partition onto I C I_C I C by dropping v v v if v ∉ ∂ C v \notin\partial C v ∈ / ∂ C (for example, merging { u } 0 ∣ { v , h } 1 \{u\}_0 \mid\{v,h\}_1 { u } 0 ∣ { v , h } 1 and { v , w } 0 ∣ { h } 0 \{v,w\}_0 \mid\{h\}_0 { v , w } 0 ∣ { h } 0 with v ∉ ∂ C v \notin\partial C v ∈ / ∂ C and v h vh v h omitted yields { u } 0 ∣ { w , h } 1 \{u\}_0 \mid\{w,h\}_1 { u } 0 ∣ { w , h } 1 ) and update that state’s table entry in O ( 1 ) O(1) O ( 1 ) time with the sum of the two child cost triples plus ( 0 , 1 , 1 ) (0, 1, 1) ( 0 , 1 , 1 ) per selected local spoke.
Root selection. At the root P 0 P_0 P 0 , where I P 0 = { r 0 , h } I_{P_0} = \{r_0,h\} I P 0 = { r 0 , h } , we accept the states in which there is a single terminal-bearing group and it contains r 0 r_0 r 0 —namely { r 0 , h } 1 \{r_0,h\}_1 { r 0 , h } 1 (when the hub is used) and { r 0 } 1 ∣ { h } 0 \{r_0\}_1 \mid\{h\}_0 { r 0 } 1 ∣ { h } 0 (when the hub is unused), whereas { r 0 } 1 ∣ { h } 1 \{r_0\}_1 \mid\{h\}_1 { r 0 } 1 ∣ { h } 1 is rejected because its terminals lie in two disconnected components—and take the minimum cost triple over the accepted states.
Lemma 4.2 (Static top-tree DP on J t J_t J t ). Given the top-tree hierarchy on P 0 P_0 P 0 , the DP tables of all clusters can be computed in O ( n ) O(n) O ( n ) time and O ( n ) O(n) O ( n ) space, and the root table returns a Steiner tree T t J T_t^J T t J connecting R R R in J t J_t J t that minimizes (7) .
Proof. The leaf and merge rules reject cycles and stranded terminals, and the root check requires all terminals to be connected to r 0 r_0 r 0 , ensuring feasibility. Optimality follows by induction on the cluster tree: any two partial solutions within a cluster C C C that induce the same partition and terminal bits on I C I_C I C are interchangeable with respect to any completion outside C C C , and the transitions exhaust all local edge and spoke choices. Since there are O ( n ) O(n) O ( n ) clusters and each table has O ( 1 ) O(1) O ( 1 ) states updated in O ( 1 ) O(1) O ( 1 ) time, total time and space are O ( n ) O(n) O ( n ) .
Dynamic maintenance and representative extraction. Because the top-tree hierarchy on P 0 P_0 P 0 has height O ( log n ) O(\log n) O ( log n ) and remains fixed throughout the phase, toggling the availability of a single edge of P 0 P_0 P 0 or spoke only requires recomputing the DP tables along the path from its assigned cluster to the root, updating O ( log n ) O(\log n) O ( log n ) tables in O ( 1 ) O(1) O ( 1 ) time each. Since each graph update in G t G_t G t toggles O ( 1 ) O(1) O ( 1 ) edges and spokes in J t J_t J t , maintaining T t J T_t^J T t J takes O ( log n ) O(\log n) O ( log n ) time per update.
Lemma 4.3 (Dynamic maintenance on J t J_t J t ). The top-tree DP can be initialized at the start of a phase in O ( n log n ) O(n\log n) O ( n log n ) time and O ( n ) O(n) O ( n ) space, maintains the exact optimum T t J T_t^J T t J minimizing (7) in O ( log n ) O(\log n) O ( log n ) time per edge or spoke toggle, and supports:
(i) reading Λ ( T t J ) \Lambda(T_t^J) Λ ( T t J ) in O ( 1 ) O(1) O ( 1 ) time at the root;
(ii) extracting the representative set Q t Q_t Q t in O ( ∣ Q t ∣ log n ) = O ( B log n ) O(|Q_t|\log n)=O(B\log n) O ( ∣ Q t ∣ log n ) = O ( B log n ) time; and
(iii) reporting the edges of F t = T t J − h F_t=T_t^J-h F t = T t J − h in O ( ∣ E ( F t ) ∣ log n ) = O ( n log n ) O(|E(F_t)|\log n)=O(n\log n) O ( ∣ E ( F t ) ∣ log n ) = O ( n log n ) time.
Proof. Constructing the top-tree hierarchy on P 0 P_0 P 0 and exposing r 0 r_0 r 0 takes O ( n log n ) O(n\log n) O ( n log n ) time [3 ] , and initializing all DP tables takes O ( n ) O(n) O ( n ) time and space by Lemma 4.2. Each availability toggle affects only the O ( log n ) O(\log n) O ( log n ) ancestors of the edge’s or spoke’s assigned cluster, each recomputed in O ( 1 ) O(1) O ( 1 ) time, and Λ ( T t J ) \Lambda(T_t^J) Λ ( T t J ) is stored at the root.
To extract Q t Q_t Q t without listing F t F_t F t , we inspect the optimal root entry: if its spoke count is zero, we return Q t = { r 0 } Q_t=\{r_0\} Q t = { r 0 } in O ( 1 ) O(1) O ( 1 ) time; otherwise, we follow its backpointers down the hierarchy, reporting locally selected spoke endpoints and recursing only into child entries with positive spoke count. Since each of the ∣ Q t ∣ ≤ max { 1 , ∣ Z t ∣ } = O ( B ) |Q_t|\le\max\{1,|Z_t|\}=O(B) ∣ Q t ∣ ≤ max { 1 , ∣ Z t ∣ } = O ( B ) selected spokes is reached along a root-to-cluster path of length O ( log n ) O(\log n) O ( log n ) , this takes O ( ∣ Q t ∣ log n ) = O ( B log n ) O(|Q_t|\log n)=O(B\log n) O ( ∣ Q t ∣ log n ) = O ( B log n ) time.
Similarly, to report E ( F t ) E(F_t) E ( F t ) , we follow backpointers from the root and recurse only into child entries whose P 0 P_0 P 0 -edge count (total edges minus spokes in (7)) is positive, taking O ( ∣ E ( F t ) ∣ log n ) = O ( n log n ) O(|E(F_t)|\log n)=O(n\log n) O ( ∣ E ( F t ) ∣ log n ) = O ( n log n ) time. □
In our algorithm, we initialize the top-tree hierarchy at the beginning of each phase with all edges of P 0 P_0 P 0 enabled and all spokes disabled. Each graph update generates only O ( 1 ) O(1) O ( 1 ) edge and spoke toggles, so maintaining the DP takes O ( log n ) O(\log n) O ( log n ) time per update. Moreover, J t J_t J t always contains a feasible Steiner tree: whenever an edge u v uv uv of P 0 P_0 P 0 is disabled, the spokes u h uh u h and v h vh v h are enabled, providing the replacement path u u u –h h h –v v v . Replacing disabled edges in P 0 P_0 P 0 by these paths preserves connectivity among all terminals. Thus, a connected subgraph containing R R R always exists in J t J_t J t .
Reconnecting Surviving Components
The forest F t = T t J − h F_t=T_t^J-h F t = T t J − h already connects all original terminals within each of its connected components; by Lemma 4.1 , reconnecting those components into a Steiner tree for R R R reduces to connecting their representatives Q t Q_t Q t in the current graph G t G_t G t . Running Mehlhorn’s terminal-MST algorithm on G t G_t G t or even on the current spanner S t S_t S t after every update would be too slow for sublinear update time. Instead, we decouple per-update cost estimation from tree reporting:
after each update, we run Mehlhorn’s algorithm on the explicit HLS distance sparsifier H t H_t H t (which has only O ( B n γ ) O(Bn^\gamma) O ( B n γ ) vertices and edges) to compute an MST M H M_H M H of K H t ( Q t ) K_{H_t}(Q_t) K H t ( Q t ) and update the reconnection cost estimate σ w K H t ( Q t ) ( M H ) \sigma w_{K_{H_t}(Q_t)}(M_H) σ w K H t ( Q t ) ( M H ) ; and
because H t H_t H t is a non-subgraph sparsifier whose edges are virtual shortcuts rather than edges of G t G_t G t , whenever an explicit Steiner tree is requested we instead run Mehlhorn’s construction and coherent expansion on the current dynamic spanner S t S_t S t with terminal set Q t Q_t Q t to obtain a tree A S ⊆ S t A_S\subseteq S_t A S ⊆ S t connecting Q t Q_t Q t .
Below, we first show how to maintain a designated vertex set in H t H_t H t that always contains Q t Q_t Q t while changing by only O ( 1 ) O(1) O ( 1 ) vertices per graph update, and then describe how to estimate the reconnection cost on H t H_t H t and materialize the reconnection tree on S t S_t S t .
Maintaining a larger designated set. Using Q t Q_t Q t itself as the sparsifier’s designated set would be costly: the representative set Q t Q_t Q t extracted from T t J T_t^J T t J may change substantially after each graph update, causing the top-tree DP to switch which components of P 0 − D t P_0-D_t P 0 − D t connect to the hub, changing Ω ( B ) \Omega(B) Ω ( B ) vertices of Q t Q_t Q t at once. Instead, as the sparsifier’s designated set, we use
U t = Z t ∪ { r 0 } (8) U_t = Z_t \cup\{r_0\} \tag*{(8)} U t = Z t ∪ { r 0 } (8)
containing the root terminal r 0 r_0 r 0 and all active vertices Z t Z_t Z t accumulated so far in the current phase. Since every enabled spoke has its P 0 P_0 P 0 -endpoint in Z t Z_t Z t (and Q t = { r 0 } Q_t = \{r_0\} Q t = { r 0 } when no spoke is used), we always have Q t ⊆ U t Q_t \subseteq U_t Q t ⊆ U t , so the distance guarantees of H t H_t H t on U t U_t U t automatically hold for all pairs in Q t Q_t Q t . Moreover, U t U_t U t changes by only O ( 1 ) O(1) O ( 1 ) vertices per graph update: we initialize U t = { r 0 } U_t = \{r_0\} U t = { r 0 } at the start of the algorithm, insert the at most two newly active vertices into U t U_t U t after each update in O ( n η ) O(n^\eta) O ( n η ) amortized time (Theorem 2.5 ), and remove the O ( B ) O(B) O ( B ) active vertices from the ending phase at each phase boundary in O ( B n η ) O(Bn^\eta) O ( B n η ) total time (or O ( n η ) O(n^\eta) O ( n η ) amortized time per update). Throughout each phase, ∣ U t ∣ = O ( B ) |U_t| = O(B) ∣ U t ∣ = O ( B ) , so Theorem 2.5 guarantees
∣ V ( H t ) ∣ + ∣ E ( H t ) ∣ = O ( ∣ U t ∣ n η ) = O ( B n η ) . |V(H_t)| + |E(H_t)| = O(|U_t|n^\eta) = O(Bn^\eta). ∣ V ( H t ) ∣ + ∣ E ( H t ) ∣ = O ( ∣ U t ∣ n η ) = O ( B n η ) .
Representative reconnection. After extracting Q t Q_t Q t from the top-tree DP, we run Mehlhorn’s construction (Theorem 2.8) on the sparsifier H t H_t H t with terminal set Q t Q_t Q t (running multi-source Dijkstra from Q t Q_t Q t rather than all of U t U_t U t or R R R ). This computes an exact MST M H M_H M H of K H t ( Q t ) K_{H_t}(Q_t) K H t ( Q t ) in O ~ ( ∣ V ( H t ) ∣ + ∣ E ( H t ) ∣ ) = O ~ ( B n η ) \widetilde{O}(|V(H_t)| + |E(H_t)|) = \widetilde{O}(Bn^\eta) O ( ∣ V ( H t ) ∣ + ∣ E ( H t ) ∣ ) = O ( B n η ) deterministic time, and we store the cost upper bound c t = w ( F t ) + σ w K H t ( Q t ) ( M H ) c_t = w(F_t) + \sigma w_{K_{H_t}(Q_t)}(M_H) c t = w ( F t ) + σ w K H t ( Q t ) ( M H ) . When an explicit Steiner tree is requested, we run Mehlhorn’s construction (Theorem 2.8) on the current spanner S t S_t S t with terminal set Q t Q_t Q t to compute an MST M S M_S M S of K S t ( Q t ) K_{S_t}(Q_t) K S t ( Q t ) , coherently expand M S M_S M S along its owner forest in S t S_t S t into a tree A S ⊆ S t A_S \subseteq S_t A S ⊆ S t (Lemma 2.9 ), and in F t ∪ A S F_t \cup A_S F t ∪ A S delete cycles and prune leaves outside R R R .
Lemma 4.4. Maintaining the designated set U t = Z t ∪ { r 0 } U_t = Z_t \cup\{r_0\} U t = Z t ∪ { r 0 } in the HLS sparsifier H t H_t H t takes O ( n η ) O(n^\eta) O ( n η ) amortized time per graph update and O ( B n η ) O(Bn^\eta) O ( B n η ) amortized time for the O ( B ) O(B) O ( B ) vertex deletions at each phase boundary, ensuring Q t ⊆ U t Q_t \subseteq U_t Q t ⊆ U t and ∣ V ( H t ) ∣ + ∣ E ( H t ) ∣ = O ( B n η ) |V(H_t)| + |E(H_t)| = O(Bn^\eta) ∣ V ( H t ) ∣ + ∣ E ( H t ) ∣ = O ( B n η ) throughout. After each update, computing the MST M H M_H M H of K H t ( Q t ) K_{H_t}(Q_t) K H t ( Q t ) and updating the cost estimate c t c_t c t takes O ~ ( B n η ) \widetilde{O}(Bn^\eta) O ( B n η ) deterministic time.
Approximation Analysis
We now turn to analyzing the approximation factor achieved by our algorithm against the optimum in the current graph G t G_t G t . We bound the approximation factor in two steps. In § 5.1 , we first show that the surviving forest F t F_t F t has weight at most 2 σ OPT G t ( R ) 2\sigma\operatorname{OPT}_{G_t}(R) 2 σ OPT G t ( R ) , and in § 5.2 we show that the tree A S ⊆ S t A_S \subseteq S_t A S ⊆ S t obtained by Mehlhorn’s construction on the current spanner S t S_t S t reconnects the component representatives Q t Q_t Q t in G t G_t G t at cost bounded by the scaled sparsifier MST weight σ w K H t ( Q t ) ( M H ) \sigma w_{K_{H_t}(Q_t)}(M_H) σ w K H t ( Q t ) ( M H ) and proportional to OPT G t ( R ) \operatorname{OPT}_{G_t}(R) OPT G t ( R ) . Combining the surviving forest with this reconnection tree establishes our constant-factor approximation guarantee for integer weights (Theorem 4.9 ), which Lemma 4.10 then extends to polynomially bounded real weights.
Bounding the Surviving Forest Cost
Consider a minimum Steiner tree T ∗ T^* T ∗ connecting R R R in G t G_t G t . Removing all newly inserted edges (i.e., those inserted during the current phase) from T ∗ T^* T ∗ leaves components consisting only of surviving phase-start edges of G ∘ G^\circ G ∘ . Because hub spokes have weight zero in J t J_t J t (their reconnection cost is paid in Section 4.4.2), the weight of T J ∗ T^*_J T J ∗ in J t J_t J t equals the weight w ( F t ) w(F_t) w ( F t ) of its P 0 P_0 P 0 -edges. Moreover, since T J ∗ T^*_J T J ∗ is a minimum-weight Steiner tree in J t J_t J t , we can upper-bound w ( F t ) w(F_t) w ( F t ) by using the surviving components of T ∗ T^* T ∗ to construct a feasible Steiner tree in J t J_t J t of weight at most 2 σ w ( T ∗ ) 2\sigma w(T^*) 2 σ w ( T ∗ ) .
The next lemma shows how to route each terminal-bearing component K K K of T ∗ T^* T ∗ in the frozen terminal metric K S ( R ) K_S(R) K S ( R ) , so that its terminals are connected both to one another and to an active terminal a ( x ) ∈ A t a(x) \in A_t a ( x ) ∈ A t , at total cost at most 2 σ w ( K ) 2\sigma w(K) 2 σ w ( K ) . Rather than doubling all edges of K K K in a closed tour, we traverse K K K from an endpoint x ∈ V ( K ) x \in V(K) x ∈ V ( K ) of a newly inserted edge to a terminal r ∈ V ( K ) ∩ R r \in V(K) \cap R r ∈ V ( K ) ∩ R and use the weight along the x x x –r r r path to pay for routing from x x x to its nearest terminal a ( x ) a(x) a ( x ) in S S S .
Lemma 4.5. Suppose T ∗ T^* T ∗ uses at least one newly inserted edge. Let K K K be a terminal-containing component after all such edges are removed. Each such K K K contains a vertex x x x incident to a removed newly inserted edge, whose owner a ( x ) a(x) a ( x ) in the frozen spanner S S S has an enabled spoke a ( x ) h a(x)h a ( x ) h . The terminals V ( K ) ∩ R V(K) \cap R V ( K ) ∩ R , together with a ( x ) a(x) a ( x ) , are spanned by a connected subgraph in K S ( R ) K_S(R) K S ( R ) of weight at most 2 σ w ( K ) 2\sigma w(K) 2 σ w ( K ) .
Proof. First, such an endpoint x x x must exist. Because T ∗ T^* T ∗ is a tree and at least one newly inserted edge is removed, at least two components remain. Each component K K K was connected to the other components only through removed newly inserted edges, so it contains at least one vertex x x x incident to such an edge. The owner a ( x ) a(x) a ( x ) of x x x in the frozen spanner S S S was added to A t A_t A t when that edge was inserted, so the spoke a ( x ) h a(x)h a ( x ) h is available.
Next, we fix any terminal r ∈ V ( K ) ∩ R r \in V(K) \cap R r ∈ V ( K ) ∩ R . Since K K K is a component obtained by deleting edges from the tree T ∗ T^* T ∗ , it is also a tree; let d K ( x , r ) d_K(x,r) d K ( x , r ) be the length of its unique x x x –r r r path. Starting at x x x , we progress along this path: at each path vertex, we first explore every subtree attached outside the path by a depth-first traversal, returning to that vertex before advancing to the next path vertex, and at r r r we finish exploring its attached subtrees and stop. This walk, denoted by W W W , visits every vertex of K K K , traversing each path edge once and every other edge twice, as illustrated in Figure 3 . Its length is
Figure 3. After removing the newly inserted edge x y xy x y , its endpoints lie in surviving components K K K and K ′ K' K ′ , and their frozen owners have enabled zero-weight spokes to h h h . In K K K , the unique x x x –r r r path is highlighted in blue and has length d K ( x , r ) d_K(x,r) d K ( x , r ) . At each vertex on the blue path, the red walk explores the off-path subtrees and returns to that vertex before moving to the next vertex. At r r r , it explores the remaining subtrees, returns to r r r , and stops. Path edges are traversed once and all other edges twice, giving length 2 w ( K ) − d K ( x , r ) 2w(K)-d_K(x,r) 2 w ( K ) − d K ( x , r ) .
w ( W ) = 2 w ( K ) − d K ( x , r ) . w(W) = 2w(K) - d_K(x,r). w ( W ) = 2 w ( K ) − d K ( x , r ) .
Every edge of W W W survives from G ∘ G^\circ G ∘ . For each traversal of an edge u v uv uv in W W W , we replace it by a shortest u u u –v v v path in the frozen spanner S S S , which has length
d S ( u , v ) ≤ σ d G ∘ ( u , v ) ( S is a σ -spanner of G ∘ ) ≤ σ w ( u v ) ( u v itself is a path in G ∘ ) . \begin{aligned}
d_S(u,v) &\le\sigma d_{G^\circ}(u,v) && (S\text{ is a }\sigma\text{-spanner of }G^\circ) \\
&\le\sigma w(uv) && (uv\text{ itself is a path in }G^\circ).
\end{aligned} d S ( u , v ) ≤ σ d G ∘ ( u , v ) ≤ σ w ( uv ) ( S is a σ -spanner of G ∘ ) ( uv itself is a path in G ∘ ) .
Let W S W_S W S be the resulting walk in S S S , obtained by concatenating the shortest paths that replace successive edge traversals of W W W . Summing over the edge traversals of W W W , with repetitions, gives
w ( W S ) = ∑ u v ∈ W d S ( u , v ) ≤ σ ∑ u v ∈ W w ( u v ) = σ ( 2 w ( K ) − d K ( x , r ) ) . w(W_S) = \sum_{uv \in W} d_S(u,v) \le\sigma\sum_{uv \in W} w(uv) = \sigma(2w(K)-d_K(x,r)). w ( W S ) = uv ∈ W ∑ d S ( u , v ) ≤ σ uv ∈ W ∑ w ( uv ) = σ ( 2 w ( K ) − d K ( x , r )) .
The shortest path from a ( x ) a(x) a ( x ) to x x x in the frozen spanner S S S has length
δ ( x ) = d S ( a ( x ) , x ) ≤ d S ( r , x ) ( a ( x ) is the nearest terminal to x ; r ∈ R ) ≤ σ d G ∘ ( r , x ) ( S is a σ -spanner of G ∘ ) ≤ σ d K ( r , x ) ( K ⊆ G ∘ ) . \begin{aligned}
\delta(x) &= d_S(a(x),x)\\
&\le d_S(r,x) && (a(x)\text{ is the nearest terminal to }x;\ r\in R)\\
&\le\sigma d_{G^\circ}(r,x) && (S\text{ is a }\sigma\text{-spanner of }G^\circ)\\
&\le\sigma d_K(r,x) && (K\subseteq G^\circ).
\end{aligned} δ ( x ) = d S ( a ( x ) , x ) ≤ d S ( r , x ) ≤ σ d G ∘ ( r , x ) ≤ σ d K ( r , x ) ( a ( x ) is the nearest terminal to x ; r ∈ R ) ( S is a σ -spanner of G ∘ ) ( K ⊆ G ∘ ) .
Concatenating this shortest a ( x ) a(x) a ( x ) –x x x path in S S S with W S W_S W S yields a walk in S S S that begins at a ( x ) ∈ R a(x)\in R a ( x ) ∈ R and visits every terminal in V ( K ) ∩ R V(K)\cap R V ( K ) ∩ R , of total length at most
δ ( x ) + w ( W S ) ≤ δ ( x ) + σ ( 2 w ( K ) − d K ( x , r ) ) ≤ 2 σ w ( K ) . (9) \delta(x)+w(W_S)\le\delta(x)+\sigma\bigl(2w(K)-d_K(x,r)\bigr)\le2\sigma w(K). \tag*{(9)} δ ( x ) + w ( W S ) ≤ δ ( x ) + σ ( 2 w ( K ) − d K ( x , r ) ) ≤ 2 σ w ( K ) . (9)
The subtraction in the x x x –r r r walk pays for the shortest path from a ( x ) a(x) a ( x ) to x x x in S S S .
Finally, since this walk in S S S starts at the terminal a ( x ) ∈ R a(x)\in R a ( x ) ∈ R and visits all terminals in V ( K ) ∩ R V(K)\cap R V ( K ) ∩ R , we list the visited terminals of ( V ( K ) ∩ R ) ∪ { a ( x ) } (V(K)\cap R)\cup\{a(x)\} ( V ( K ) ∩ R ) ∪ { a ( x )} in order of visit (ignoring consecutive repetitions of the same terminal) and replace the walk segment between each consecutive pair u , v u,v u , v by the metric edge u v uv uv of weight d S ( u , v ) d_S(u,v) d S ( u , v ) in K S ( R ) K_S(R) K S ( R ) . Because d S ( u , v ) d_S(u,v) d S ( u , v ) is at most the length of the walk segment in S S S between u u u and v v v , the resulting subgraph in K S ( R ) K_S(R) K S ( R ) spans ( V ( K ) ∩ R ) ∪ { a ( x ) } (V(K)\cap R)\cup\{a(x)\} ( V ( K ) ∩ R ) ∪ { a ( x )} and has weight at most (9) .
Lemma 4.5 connects the terminals of each surviving component K K K of T ∗ T^* T ∗ to an active terminal a ( x K ) a(x_K) a ( x K ) using edges of the full terminal metric K S ( R ) K_S(R) K S ( R ) , and the enabled spoke a ( x K ) h a(x_K)h a ( x K ) h links all these active terminals through the hub h h h . To turn this into a valid Steiner tree inside J t J_t J t , we use the MST augmentation property (Lemma 2.10 ) to replace the clique edges of K S ( R ) K_S(R) K S ( R ) with edges of the phase-start terminal MST T 0 T_0 T 0 , coherently expand those T 0 T_0 T 0 edges into paths in P 0 P_0 P 0 (Lemma 2.9 ), and bypass any deleted edge u v ∈ D t uv\in D_t uv ∈ D t of P 0 P_0 P 0 via the zero-weight spokes u u u –h h h –v v v .
Lemma 4.6. At any step t t t of a phase, the surviving forest F t = T t J − h F_t=T_t^J-h F t = T t J − h satisfies
w ( F t ) ≤ 2 σ OPT G t ( R ) . w(F_t)\le2\sigma\operatorname{OPT}_{G_t}(R). w ( F t ) ≤ 2 σ OPT G t ( R ) .
Proof. First suppose that T ∗ T^{*} T ∗ contains at least one newly inserted edge. For each terminal-containing component K K K of T ∗ T^{*} T ∗ after removing newly inserted edges, Lemma 4.5 provides a connected subgraph in K S ( R ) K_{S}(R) K S ( R ) spanning ( V ( K ) ∩ R ) ∪ { a ( x K ) } (V(K) \cap R) \cup\{a(x_{K})\} ( V ( K ) ∩ R ) ∪ { a ( x K )} of weight at most 2 σ w ( K ) 2\sigma w(K) 2 σ w ( K ) together with an enabled spoke a ( x K ) h a(x_{K})h a ( x K ) h . Taking the union of these subgraphs and the set E h E_{h} E h of corresponding spokes a ( x K ) h a(x_{K})h a ( x K ) h over all such components K K K yields a connected subgraph L ⊆ K S ( R ) ∪ E h L \subseteq K_{S}(R) \cup E_{h} L ⊆ K S ( R ) ∪ E h spanning R ∪ { h } R \cup\{h\} R ∪ { h } . Since spokes have weight zero in J t J_{t} J t and the components K K K are edge-disjoint subgraphs of T ∗ T^{*} T ∗ , we have
w ( L ) ≤ ∑ K 2 σ w ( K ) = 2 σ ∑ K w ( K ) ≤ 2 σ w ( T ∗ ) . w(L) \le\sum_{K} 2\sigma w(K) = 2\sigma\sum_{K} w(K) \le2\sigma w(T^{*}). w ( L ) ≤ K ∑ 2 σ w ( K ) = 2 σ K ∑ w ( K ) ≤ 2 σ w ( T ∗ ) .
Because T 0 T_{0} T 0 is an MST of K S ( R ) K_{S}(R) K S ( R ) and L L L is a connected subgraph of K S ( R ) ∪ E h K_{S}(R) \cup E_{h} K S ( R ) ∪ E h spanning R ∪ { h } R \cup\{h\} R ∪ { h } , Lemma 2.10 implies that an MST M M M of T 0 ∪ E h T_{0} \cup E_{h} T 0 ∪ E h satisfies
w ( M ) = mst ( T 0 ∪ E h ) = mst ( K S ( R ) ∪ E h ) ≤ w ( L ) ≤ 2 σ w ( T ∗ ) . w(M) = \operatorname{mst}(T_{0} \cup E_{h}) = \operatorname{mst}(K_{S}(R) \cup E_{h}) \le w(L) \le2\sigma w(T^{*}). w ( M ) = mst ( T 0 ∪ E h ) = mst ( K S ( R ) ∪ E h ) ≤ w ( L ) ≤ 2 σ w ( T ∗ ) .
Now we map M M M into the auxiliary graph J t J_{t} J t . By Lemma 2.9 , replacing the T 0 T_{0} T 0 -edges of M M M by their coherent routes in P 0 P_{0} P 0 (while keeping the spokes of M M M in E h E_{h} E h ) produces a connected subgraph of P 0 ∪ E h P_{0} \cup E_{h} P 0 ∪ E h spanning R R R of weight at most w ( M ) w(M) w ( M ) . If any edge u v ∈ E ( P 0 ) uv \in E(P_{0}) uv ∈ E ( P 0 ) used by this subgraph was deleted during the phase (u v ∈ D t uv \in D_{t} uv ∈ D t ), then both endpoints u , v ∈ end ( D t ) ⊆ Z t u,v \in\operatorname{end}(D_{t}) \subseteq Z_{t} u , v ∈ end ( D t ) ⊆ Z t have enabled zero-weight spokes u h uh u h and v h vh v h in J t J_{t} J t ; replacing each such deleted edge u v ∈ D t uv \in D_{t} uv ∈ D t by the two-spoke path u u u –h h h –v v v preserves connectivity on R R R without increasing weight. Removing cycles from the resulting connected subgraph yields a feasible Steiner tree Y Y Y in J t J_{t} J t with w ( Y ) ≤ w ( M ) ≤ 2 σ w ( T ∗ ) w(Y) \le w(M) \le2\sigma w(T^{*}) w ( Y ) ≤ w ( M ) ≤ 2 σ w ( T ∗ ) .
In the remaining case where T ∗ T^{*} T ∗ contains no newly inserted edge, we have T ∗ ⊆ G ∘ T^{*} \subseteq G^{\circ} T ∗ ⊆ G ∘ . By the metric-MST bound (Lemma 2.6 ) and the fact that S S S is a σ \sigma σ -spanner of G ∘ G^{\circ} G ∘ ,
w ( T 0 ) ≤ 2 OPT S ( R ) ≤ 2 σ OPT G ∘ ( R ) ≤ 2 σ w ( T ∗ ) . w(T_{0}) \le2\operatorname{OPT}_{S}(R) \le2\sigma\operatorname{OPT}_{G^{\circ}}(R) \le2\sigma w(T^{*}). w ( T 0 ) ≤ 2 OPT S ( R ) ≤ 2 σ OPT G ∘ ( R ) ≤ 2 σ w ( T ∗ ) .
Expanding T 0 T_{0} T 0 into P 0 P_{0} P 0 and replacing any deleted edge u v ∈ D t uv \in D_{t} uv ∈ D t by the zero-weight path u u u –h h h –v v v as above again yields a feasible Steiner tree Y Y Y in J t J_{t} J t with w ( Y ) ≤ w ( T 0 ) ≤ 2 σ w ( T ∗ ) w(Y) \le w(T_{0}) \le2\sigma w(T^{*}) w ( Y ) ≤ w ( T 0 ) ≤ 2 σ w ( T ∗ ) .
In either case, since T t J T_{t}^{J} T t J minimizes weight among all Steiner trees connecting R R R in J t J_{t} J t and its spokes have weight zero, removing the spokes from T t J T_{t}^{J} T t J leaves F t F_{t} F t with
w ( F t ) = w ( T t J ) ≤ w ( Y ) ≤ 2 σ w ( T ∗ ) = 2 σ OPT G t ( R ) . w(F_{t}) = w(T_{t}^{J}) \le w(Y) \le2\sigma w(T^{*}) = 2\sigma\operatorname{OPT}_{G_{t}}(R). w ( F t ) = w ( T t J ) ≤ w ( Y ) ≤ 2 σ w ( T ∗ ) = 2 σ OPT G t ( R ) .
Bounding the Representative Reconnection Cost
We now bound the weight of the tree A S ⊆ S t A_{S} \subseteq S_{t} A S ⊆ S t (and the stored estimate σ w K H t ( Q t ) ( M H ) \sigma w_{K H_{t}(Q_{t})}(M_{H}) σ w K H t ( Q t ) ( M H ) ) used to reconnect the surviving components of F t F_{t} F t through their representatives Q t Q_{t} Q t . Because Q t Q_{t} Q t may include non-terminal vertices of P 0 P_{0} P 0 , we first bound the optimal cost OPT G t ( Q t ) \operatorname{OPT}_{G_{t}}(Q_{t}) OPT G t ( Q t ) of connecting Q t Q_{t} Q t in G t G_{t} G t in terms of OPT G t ( R ) \operatorname{OPT}_{G_{t}}(R) OPT G t ( R ) (Lemma 4.7), and then show that A S A_{S} A S and σ w K H t ( Q t ) ( M H ) \sigma w_{K H_{t}(Q_{t})}(M_{H}) σ w K H t ( Q t ) ( M H ) connect Q t Q_{t} Q t within a 2 σ ρ η 2\sigma\rho_{\eta} 2 σ ρ η factor.
Lemma 4.7. At any step t t t of a phase, the minimum Steiner tree weight for the representative set Q t Q_{t} Q t in G t G_{t} G t satisfies
OPT G t ( Q t ) ≤ w ( F t ) + OPT G t ( R ) ≤ ( 1 + 2 σ ) OPT G t ( R ) . \operatorname{OPT}_{G_{t}}(Q_{t}) \le w(F_{t}) + \operatorname{OPT}_{G_{t}}(R) \le(1+2\sigma)\operatorname{OPT}_{G_{t}}(R). OPT G t ( Q t ) ≤ w ( F t ) + OPT G t ( R ) ≤ ( 1 + 2 σ ) OPT G t ( R ) . Proof. By Lemma 4.1 , each representative in Q t Q_{t} Q t belongs to a component of F t F_{t} F t that also contains a terminal in R R R . Consequently, the union of F t F_{t} F t with a minimum Steiner tree for R R R in G t G_{t} G t connects all vertices of Q t Q_{t} Q t and has weight at most w ( F t ) + OPT G t ( R ) w(F_{t}) + \operatorname{OPT}_{G_{t}}(R) w ( F t ) + OPT G t ( R ) , proving the first inequality; Lemma 4.6 then gives the second.
Having related OPT G t ( Q t ) \operatorname{OPT}_{G_t}(Q_t) OPT G t ( Q t ) to OPT G t ( R ) \operatorname{OPT}_{G_t}(R) OPT G t ( R ) , we next bound both the scaled sparsifier MST weight σ w K H t ( Q t ) ( M H ) \sigma w_{K_{H_t}(Q_t)}(M_H) σ w K H t ( Q t ) ( M H ) and the weight of the tree A S ⊆ S t A_S \subseteq S_t A S ⊆ S t obtained by coherently expanding the terminal-metric MST M S M_S M S of K S t ( Q t ) K_{S_t}(Q_t) K S t ( Q t ) .
Lemma 4.8. At any step t t t of a phase, the tree A S ⊆ S t A_S \subseteq S_t A S ⊆ S t connects all representatives in Q t Q_t Q t in G t G_t G t and satisfies
w ( A S ) ≤ σ w K H t ( Q t ) ( M H ) ≤ 2 σ ρ η OPT G t ( Q t ) . w(A_S) \leq\sigma w_{K_{H_t}(Q_t)}(M_H) \leq2\sigma\rho_\eta\operatorname{OPT}_{G_t}(Q_t). w ( A S ) ≤ σ w K H t ( Q t ) ( M H ) ≤ 2 σ ρ η OPT G t ( Q t ) .
Proof. Let M G M_G M G be an MST of K G t ( Q t ) K_{G_t}(Q_t) K G t ( Q t ) , used only for analysis. Since both K H t ( Q t ) K_{H_t}(Q_t) K H t ( Q t ) and K G t ( Q t ) K_{G_t}(Q_t) K G t ( Q t ) are complete graphs on Q t Q_t Q t , the edge set of M G M_G M G also forms a spanning tree of K H t ( Q t ) K_{H_t}(Q_t) K H t ( Q t ) , where each edge u v ∈ E ( M G ) uv \in E(M_G) uv ∈ E ( M G ) has weight d H t ( u , v ) d_{H_t}(u,v) d H t ( u , v ) instead of d G t ( u , v ) d_{G_t}(u,v) d G t ( u , v ) . Therefore,
\begin{aligned}
w_{K_{H_t}(Q_t)}(M_H) &\leq w_{K_{H_t}(Q_t)}(M_G) && (M_H\text{ is an MST of }K_{H_t}(Q_t))\\
&= \sum_{uv\in E(M_G)} d_{H_t}(u,v)\\
&\leq\rho_\eta\sum_{uv\in E(M_G)} d_{G_t}(u,v) && (\text{sparsifier stretch, {xref}`Theorem 2.5`, since }Q_t\subseteq U_t)\\
&= \rho_\eta w_{K_{G_t}(Q_t)}(M_G)\\
&\leq2\rho_\eta\operatorname{OPT}_{G_t}(Q_t) && (\text{the metric-MST bound, {xref}`Lemma 2.6`).
\end{aligned}} \tag*{(10)}\end{aligned}
Similarly, since M S M_S M S is an MST of K S t ( Q t ) K_{S_t}(Q_t) K S t ( Q t ) and M H M_H M H is a spanning tree on the same vertex set Q t Q_t Q t , expanding M S M_S M S coherently in S t S_t S t (Lemma 2.9 ) produces a tree A S ⊆ S t ⊆ G t A_S \subseteq S_t \subseteq G_t A S ⊆ S t ⊆ G t connecting Q t Q_t Q t with
\begin{aligned}
w(A_S) &\leq w_{K_{S_t}(Q_t)}(M_S) && (\text{the union counts shared edges only once, {xref}`Lemma 2.9`)\\
&\leq w_{K_{S_t}(Q_t)}(M_H) && (M_S\text{ is an MST of }K_{S_t}(Q_t))\\
&= \sum_{uv\in E(M_H)} d_{S_t}(u,v)\\
&\leq\sigma\sum_{uv\in E(M_H)} d_{G_t}(u,v) && (\text{spanner stretch, {xref}`Theorem 2.2`)\\
&\leq\sigma\sum_{uv\in E(M_H)} d_{H_t}(u,v) && (\text{noncontraction, {xref}`Theorem 2.5`)\\
&= \sigma w_{K_{H_t}(Q_t)}(M_H)\\
&\leq2\sigma\rho_\eta\operatorname{OPT}_{G_t}(Q_t) && (\text{Inequality {xref}`(11)`}).
\end{aligned}}}} \tag*{(11)}\end{aligned}
Combining the bound on the surviving forest F t F_t F t (Lemma 4.6) with the bounds on the reconnection tree A S A_S A S and stored cost estimate c t c_t c t (Lemmas 4.7 and 4.8) yields our approximation guarantee for integer-weighted graph G t G_t G t .
Theorem 4.9. For positive polynomially bounded integer edge weights, the Steiner tree T t T_t T t maintained by the algorithm in G t G_t G t and the stored cost estimate c t = w ( F t ) + σ w K H t ( Q t ) ( M H ) c_t = w(F_t) + \sigma w_{K_{H_t}(Q_t)}(M_H) c t = w ( F t ) + σ w K H t ( Q t ) ( M H ) satisfy
OPT G t ( R ) ≤ w ( T t ) ≤ c t ≤ [ 2 σ + 2 σ ρ η ( 1 + 2 σ ) ] OPT G t ( R ) . \operatorname{OPT}_{G_t}(R) \leq w(T_t) \leq c_t \leq[2\sigma+ 2\sigma\rho_\eta(1+2\sigma)]\operatorname{OPT}_{G_t}(R). OPT G t ( R ) ≤ w ( T t ) ≤ c t ≤ [ 2 σ + 2 σ ρ η ( 1 + 2 σ )] OPT G t ( R ) .
Proof. The union F t ∪ A S F_t \cup A_S F t ∪ A S connects all original terminals. Removing cycles to obtain a spanning tree and then pruning leaves outside R R R gives a Steiner tree T t T_t T t for R R R satisfying
OPT G t ( R ) ≤ w ( T t ) ≤ w ( F t ) + w ( A S ) ≤ w ( F t ) + σ w K H t ( Q t ) ( M H ) = c t (xref‘Lemma 4.8‘) ≤ 2 σ OPT G t ( R ) + 2 σ ρ η OPT G t ( Q t ) (xref‘Lemmas 4.6 and 4.8‘) ≤ 2 σ OPT G t ( R ) + 2 σ ρ η ( 1 + 2 σ ) OPT G t ( R ) (xref‘Lemma 4.7‘) = [ 2 σ + 2 σ ρ η ( 1 + 2 σ ) ] OPT G t ( R ) . \begin{aligned}
\operatorname{OPT}_{G_t}(R) &\le w(T_t) \le w(F_t) + w(A_S) \\
&\le w(F_t) + \sigma w_{K_{H_t}(Q_t)}(M_H) = c_t && \text{({xref}`Lemma 4.8`)} \\
&\le2\sigma\operatorname{OPT}_{G_t}(R) + 2\sigma\rho\eta\operatorname{OPT}_{G_t}(Q_t) && \text{({xref}`Lemmas 4.6 and 4.8`)} \\
&\le2\sigma\operatorname{OPT}_{G_t}(R) + 2\sigma\rho\eta(1 + 2\sigma) \operatorname{OPT}_{G_t}(R) && \text{({xref}`Lemma 4.7`)} \\
&= [2\sigma+ 2\sigma\rho\eta(1 + 2\sigma)]\operatorname{OPT}_{G_t}(R).
\end{aligned} OPT G t ( R ) ≤ w ( T t ) ≤ w ( F t ) + w ( A S ) ≤ w ( F t ) + σ w K H t ( Q t ) ( M H ) = c t ≤ 2 σ OPT G t ( R ) + 2 σ ρ η OPT G t ( Q t ) ≤ 2 σ OPT G t ( R ) + 2 σ ρ η ( 1 + 2 σ ) OPT G t ( R ) = [ 2 σ + 2 σ ρ η ( 1 + 2 σ )] OPT G t ( R ) . ( xref ‘Lemma 4.8‘) ( xref ‘Lemmas 4.6 and 4.8‘) ( xref ‘Lemma 4.7‘)
Thus, c t c_t c t upper-bounds the reported tree’s cost and is a constant-factor approximation to the current optimum.
Returning to real weights. We now transfer the approximation guarantee from the rounded integer weights w ^ ( e ) = ⌈ w ( e ) / ϵ ⌉ \widehat{w}(e) = \lceil w(e)/\epsilon\rceil w ( e ) = ⌈ w ( e ) / ϵ ⌉ (for fixed ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) ) to the original real weights w ( e ) ∈ [ 1 , W ] w(e) \in[1,W] w ( e ) ∈ [ 1 , W ] at the cost of a ( 1 + ϵ ) (1+\epsilon) ( 1 + ϵ ) factor.
Since ⌈ x ⌉ ∈ [ x , x + 1 ) \lceil x\rceil\in[x,x+1) ⌈ x ⌉ ∈ [ x , x + 1 ) and w ( e ) ≥ 1 w(e) \ge1 w ( e ) ≥ 1 , every edge e e e satisfies
w ( e ) ≤ ϵ ⌈ w ( e ) ϵ ⌉ = ϵ w ^ ( e ) ≤ ϵ ( w ( e ) ϵ + 1 ) = w ( e ) + ϵ ≤ ( 1 + ϵ ) w ( e ) . (12) w(e) \le\epsilon\left\lceil\frac{w(e)}{\epsilon}\right\rceil= \epsilon\widehat{w}(e) \le\epsilon\left(\frac{w(e)}{\epsilon}+1\right) = w(e)+\epsilon\le(1+\epsilon)w(e). \tag*{(12)} w ( e ) ≤ ϵ ⌈ ϵ w ( e ) ⌉ = ϵ w ( e ) ≤ ϵ ( ϵ w ( e ) + 1 ) = w ( e ) + ϵ ≤ ( 1 + ϵ ) w ( e ) . (12)
For fixed ϵ \epsilon ϵ , the maximum integer weight ⌈ W / ϵ ⌉ \lceil W/\epsilon\rceil ⌈ W / ϵ ⌉ remains polynomial in n n n . Moreover, because rounding only rescales edge weights, both instances share the exact same set of feasible Steiner trees.
Lemma 4.10. A C C C -approximation in the integer-weighted instance gives a C ( 1 + ϵ ) C(1+\epsilon) C ( 1 + ϵ ) -approximation in the original real-weighted instance. Rounding takes O ( m 0 ) O(m_0) O ( m 0 ) initial time and O ( 1 ) O(1) O ( 1 ) additional time per update.
Proof. Summing (12) over the edges of any subgraph H H H gives w ( H ) ≤ ϵ w ^ ( H ) ≤ ( 1 + ϵ ) w ( H ) w(H) \le\epsilon\widehat{w}(H) \le(1+\epsilon)w(H) w ( H ) ≤ ϵ w ( H ) ≤ ( 1 + ϵ ) w ( H ) . Let T T T be the C C C -approximate Steiner tree returned in the integer instance (with optimum OPT ^ \widehat{\operatorname{OPT}} OPT ), and let T ∗ T^* T ∗ be an optimal Steiner tree under the original weights w w w . Since T ∗ T^* T ∗ is also a feasible Steiner tree in the integer instance, OPT ^ ≤ w ^ ( T ∗ ) \widehat{\operatorname{OPT}} \le\widehat{w}(T^*) OPT ≤ w ( T ∗ ) , and therefore
w ( T ) ≤ ϵ w ^ ( T ) ≤ ϵ C OPT ^ ≤ ϵ C w ^ ( T ∗ ) ≤ C ( 1 + ϵ ) w ( T ∗ ) = C ( 1 + ϵ ) OPT G t ( R ) . w(T) \le\epsilon\widehat{w}(T) \le\epsilon C\widehat{\operatorname{OPT}} \le\epsilon C\widehat{w}(T^*) \le C(1+\epsilon)w(T^*) = C(1+\epsilon)\operatorname{OPT}_{G_t}(R). w ( T ) ≤ ϵ w ( T ) ≤ ϵ C OPT ≤ ϵ C w ( T ∗ ) ≤ C ( 1 + ϵ ) w ( T ∗ ) = C ( 1 + ϵ ) OPT G t ( R ) .
Evaluating w ^ ( e ) = ⌈ w ( e ) / ϵ ⌉ \widehat{w}(e) = \lceil w(e)/\epsilon\rceil w ( e ) = ⌈ w ( e ) / ϵ ⌉ takes O ( 1 ) O(1) O ( 1 ) time per edge, giving O ( m 0 ) O(m_0) O ( m 0 ) initial time and O ( 1 ) O(1) O ( 1 ) time per edge update.
Taking C = 2 σ + 2 σ ρ η ( 1 + 2 σ ) C = 2\sigma+ 2\sigma\rho\eta(1+2\sigma) C = 2 σ + 2 σ ρ η ( 1 + 2 σ ) , we get approximation factor ( 1 + ϵ ) [ 2 σ + 2 σ ρ η ( 1 + 2 σ ) ] (1+\epsilon)[2\sigma+ 2\sigma\rho\eta(1+2\sigma)] ( 1 + ϵ ) [ 2 σ + 2 σ ρ η ( 1 + 2 σ )] . Under the original real weights, return ϵ c t \epsilon c_t ϵ c t for a cost-estimation query; this upper-bounds the reported tree’s cost and satisfies the same C ( 1 + ϵ ) C(1+\epsilon) C ( 1 + ϵ ) approximation guarantee.
Time and Space Analysis
We now analyze the running time and space usage of our fully dynamic algorithm (Algorithm 1) for fixed approximation parameters ν \nu ν , η \eta η , ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) with ν + η < 1 \nu+\eta<1 ν + η < 1 . In § 5.4 , we first bound the running time of each of the four procedures (initialization, phase reconstruction, single-update processing, and tree reporting) in terms of the phase length B B B , and then choose B B B to balance their running times. We bound the space usage in Lemma 4.12 .
Running Time Analysis
Lemma 4.11. For fixed parameters ν , η , ε ∈ ( 0 , 1 ) \nu,\eta,\varepsilon\in(0,1) ν , η , ε ∈ ( 0 , 1 ) and phase length B ≥ 1 B \ge1 B ≥ 1 , the procedures of Algorithm 1 satisfy the following deterministic time bounds:
(i) Initialization: O ( ( m 0 + n ) n max { ν , η } ) O((m_0+n)n^{\max\{\nu,\eta\}}) O (( m 0 + n ) n m a x { ν , η } ) time.
(ii) Phase reconstruction: O ~ ( n 1 + ν / B ) + O ( n η ) \widetilde{O}(n^{1+\nu}/B) + O(n^\eta) O ( n 1 + ν / B ) + O ( n η ) amortized update time over B B B updates.
(iii) Single-update processing: O ( n ν ) + O ~ ( B n η ) O(n^\nu) + \widetilde{O}(Bn^\eta) O ( n ν ) + O ( B n η ) amortized time per update.
(iv) Tree reporting: O ~ ( n 1 + ν ) \widetilde{O}(n^{1+\nu}) O ( n 1 + ν ) worst-case time per query.
Proof. We establish the four bounds in order.
Initialization. Rounding the m 0 m_0 m 0 initial edge weights takes O ( m 0 ) O(m_0) O ( m 0 ) time (Lemma 4.10), initializing the dynamic spanner S 0 S_0 S 0 takes O ( ( m 0 + n ) n ν ) O((m_0+n)n^\nu) O (( m 0 + n ) n ν ) time (Theorem 2.2 ), and initializing the HLS sparsifier H 0 H_0 H 0 with designated set U 0 = { r 0 } U_0=\{r_0\} U 0 = { r 0 } takes O ( ( m 0 + n ) n η ) O((m_0+n)n^\eta) O (( m 0 + n ) n η ) time (Theorem 2.5 ). For the initial phase reconstruction on G 0 G_0 G 0 , the frozen spanner snapshot S ⊆ G 0 S \subseteq G_0 S ⊆ G 0 has at most m 0 m_0 m 0 edges and no active vertices need to be removed from a prior phase, so StartPhase takes O ~ ( m 0 + n ) \widetilde{O}(m_0+n) O ( m 0 + n ) time as shown next, which is absorbed by O ( ( m 0 + n ) n max { ν , η } ) O((m_0+n)n^{\max\{\nu,\eta\}}) O (( m 0 + n ) n m a x { ν , η } ) .
Phase reconstruction. Let M = ∣ E ( S ) ∣ M=|E(S)| M = ∣ E ( S ) ∣ be the number of edges in the frozen spanner snapshot S S S at the start of a phase, where M = O ( n 1 + ν ) M=O(n^{1+\nu}) M = O ( n 1 + ν ) by Theorem 2.2 . Copying S S S and running Mehlhorn’s construction to compute the owner forest and terminal-metric MST T 0 T_0 T 0 takes O ~ ( M + n ) = O ~ ( n 1 + ν ) \widetilde{O}(M+n)=\widetilde{O}(n^{1+\nu}) O ( M + n ) = O ( n 1 + ν ) time (Theorem 2.8 ), coherently expanding T 0 T_0 T 0 into the tree P 0 P_0 P 0 takes O ( n ) O(n) O ( n ) time (Lemma 2.9 ), and building the top-tree hierarchy on P 0 P_0 P 0 and initializing its DP tables takes O ( n log n ) O(n\log n) O ( n log n ) time (Lemmas 4.2 and 4.3 ). Resetting the sparsifier’s designated set U t U_t U t to { r 0 } \{r_0\} { r 0 } removes the O ( B ) O(B) O ( B ) active vertices from the preceding phase in O ( B n η ) O(Bn^\eta) O ( B n η ) amortized time (Lemma 4.4 ). Charging each rebuild after the first to the B B B updates of the preceding phase gives O ~ ( n 1 + ν / B ) + O ( n η ) \widetilde{O}(n^{1+\nu}/B)+O(n^\eta) O ( n 1 + ν / B ) + O ( n η ) amortized time per update.
Single-update processing. On each edge update, rounding its weight takes O ( 1 ) O(1) O ( 1 ) time (Lemma 4.10), updating the dynamic spanner S t S_t S t takes O ( n ν ) O(n^\nu) O ( n ν ) amortized time (Theorem 2.2 ), updating the top-tree DP on J t J_t J t for the O ( 1 ) O(1) O ( 1 ) toggled edges and spokes takes O ( log n ) O(\log n) O ( log n ) time, and extracting the representative set Q t Q_t Q t takes O ( B log n ) O(B\log n) O ( B log n ) time (Lemma 4.3 ). Forwarding the edge update to H t H_t H t and inserting the O ( 1 ) O(1) O ( 1 ) newly active vertices into U t U_t U t takes O ( n η ) O(n^\eta) O ( n η ) amortized time (Theorem 2.5 and Lemma 4.4 ), and running Mehlhorn’s construction on ( H t , Q t ) (H_t,Q_t) ( H t , Q t ) to update the cost estimate c t c_t c t takes O ~ ( B n η ) \widetilde{O}(Bn^\eta) O ( B n η ) time (Lemma 4.4 ). Summing these costs gives O ( n ν ) + O ~ ( B n η ) O(n^\nu)+\widetilde{O}(Bn^\eta) O ( n ν ) + O ( B n η ) amortized time per update.
Tree reporting. When an explicit Steiner tree is requested, recovering the edges of the forest F t F_t F t via the top-tree DP backpointers takes O ( ∣ E ( F t ) ∣ log n ) = O ( n log n ) O(|E(F_t)|\log n)=O(n\log n) O ( ∣ E ( F t ) ∣ log n ) = O ( n log n ) time (Lemma 4.3 ). Running Mehlhorn’s construction on the current spanner S t S_t S t with terminal set Q t Q_t Q t and coherently expanding the resulting terminal-metric MST M S M_S M S into the tree A S ⊆ S t A_S \subseteq S_t A S ⊆ S t takes O ~ ( ∣ E ( S t ) ∣ + n ) = O ~ ( n 1 + ν ) \widetilde{O}(|E(S_t)|+n)=\widetilde{O}(n^{1+\nu}) O ( ∣ E ( S t ) ∣ + n ) = O ( n 1 + ν ) worst-case time (Theorems 2.2 and 2.8 , and Lemma 2.9 ). Since F t F_t F t and A S A_S A S have O ( n ) O(n) O ( n ) edges in total, removing cycles and pruning non-terminal leaves in F t ∪ A S F_t \cup A_S F t ∪ A S takes O ( n ) O(n) O ( n ) time, giving O ~ ( n 1 + ν ) \widetilde{O}(n^{1+\nu}) O ( n 1 + ν ) worst-case reporting time.
Thus, any sequence of U ≥ 1 U \ge1 U ≥ 1 updates incurs total update time $\widetilde{O}(U(n^\nu+Bn^\eta)+\lceil U/B\rceil n^{1+\nu}) beyond initialization, corresponding to an amortized update time of
T u p d ( B ) = O ~ ( n 1 + ν B + n ν + B n η ) . (13) T_{\mathrm{upd}}(B)=\widetilde{O}\left(\frac{n^{1+\nu}}{B}+n^\nu+Bn^\eta\right). \tag*{(13)} T upd ( B ) = O ( B n 1 + ν + n ν + B n η ) . (13)
We balance the first and third terms by setting
B = ⌈ n ( 1 + ν − η ) / 2 ⌉ , (14) B=\left\lceil n^{(1+\nu-\eta)/2}\right\rceil, \tag*{(14)} B = ⌈ n ( 1 + ν − η ) /2 ⌉ , (14)
which (since ν < 1 \nu<1 ν < 1 and η > 0 \eta>0 η > 0 imply ( 1 + ν + η ) / 2 > ν (1+\nu+\eta)/2>\nu ( 1 + ν + η ) /2 > ν ) gives deterministic amortized update time T u p d = O ~ ( n ( 1 + ν + η ) / 2 ) T_{\mathrm{upd}}=\widetilde{O}(n^{(1+\nu+\eta)/2}) T upd = O ( n ( 1 + ν + η ) /2 ) .
Lemma 4.12. Let m t = ∣ E ( G t ) ∣ m_t=|E(G_t)| m t = ∣ E ( G t ) ∣ be the current edge count. For fixed constants ν , η ∈ ( 0 , 1 ) \nu,\eta\in(0,1) ν , η ∈ ( 0 , 1 ) with ν + η < 1 \nu+\eta<1 ν + η < 1 and our choice of B B B in (14) , the total space used is
O ( m t n max { ν , η } + n 1 + max { ν , η } ) . O\left(m_t n^{\max\{\nu,\eta\}}+n^{1+\max\{\nu,\eta\}}\right). O ( m t n m a x { ν , η } + n 1 + m a x { ν , η } ) .
Proof. Storing the current graph takes O ( m t + n ) O(m_t+n) O ( m t + n ) space; maintaining the dynamic spanner S t S_t S t , its frozen snapshot S S S , and Mehlhorn’s workspace on S S S and S t S_t S t takes O ( m t n ν + n 1 + ν ) O(m_t n^\nu+n^{1+\nu}) O ( m t n ν + n 1 + ν ) space (Theorems 2.2 and 2.8 ); maintaining the HLS sparsifier H t H_t H t takes O ( ( m t + n ) n η ) O((m_t+n)n^\eta) O (( m t + n ) n η ) space (Theorem 2.5 ); and storing the owner forest, T 0 T_0 T 0 , P 0 P_0 P 0 , and the top-tree hierarchy with its DP tables takes O ( n ) O(n) O ( n ) space (Theorem 2.8 and Lemma 4.3 ). Within a phase, maintaining A t A_t A t , D t D_t D t , Z t Z_t Z t , U t U_t U t , Q t Q_t Q t and Mehlhorn’s workspace on H t H_t H t takes O ( B n η ) O(Bn^\eta) O ( B n η ) space (Theorem 2.8 and Lemma 4.4 ). Summing these bounds gives total space
O ( m t n max { ν , η } + n 1 + max { ν , η } + B n η ) . O\left(m_t n^{\max\{\nu,\eta\}}+n^{1+\max\{\nu,\eta\}}+Bn^\eta\right). O ( m t n m a x { ν , η } + n 1 + m a x { ν , η } + B n η ) .
For B = ⌈ n ( 1 + ν − η ) / 2 ⌉ B=\left\lceil n^{(1+\nu-\eta)/2}\right\rceil B = ⌈ n ( 1 + ν − η ) /2 ⌉ and ν + η < 1 \nu+\eta<1 ν + η < 1 , we have B n η = O ( n ( 1 + ν + η ) / 2 ) = o ( n ) Bn^\eta=O(n^{(1+\nu+\eta)/2})=o(n) B n η = O ( n ( 1 + ν + η ) /2 ) = o ( n ) , leaving O ( m t n max { ν , η } + n 1 + max { ν , η } ) O(m_t n^{\max\{\nu,\eta\}}+n^{1+\max\{\nu,\eta\}}) O ( m t n m a x { ν , η } + n 1 + m a x { ν , η } ) .
Combining Theorem 4.9 and Lemma 4.10 with Lemmas 4.11 and 4.12 yields the full parameterized guarantee for our fully dynamic algorithm.
Theorem 4.13 (Parameterized version of Theorem 1.1 ). Let G G G be a connected n n n -vertex fully dynamic undirected graph with m 0 m_0 m 0 edges initially, a terminal set R R R , and polynomially bounded positive edge weights over all updates. For any fixed constants ν , η , ε ∈ ( 0 , 1 ) \nu,\eta,\varepsilon\in(0,1) ν , η , ε ∈ ( 0 , 1 ) with ν + η < 1 \nu+\eta<1 ν + η < 1 , setting σ = σ ν \sigma=\sigma_\nu σ = σ ν and B = ⌈ n ( 1 + ν − η ) / 2 ⌉ B=\left\lceil n^{(1+\nu-\eta)/2}\right\rceil B = ⌈ n ( 1 + ν − η ) /2 ⌉ gives a deterministic fully dynamic algorithm (against an adaptive adversary) that maintains a ( 1 + ε ) [ 2 σ + 2 σ ρ η ( 1 + 2 σ ) ] (1+\varepsilon)[2\sigma+2\sigma\rho_\eta(1+2\sigma)] ( 1 + ε ) [ 2 σ + 2 σ ρ η ( 1 + 2 σ )] -approximate Steiner tree for R R R in G G G (where σ ν = 2 poly ( 1 / ν ) \sigma_\nu=2^{\operatorname{poly}(1/\nu)} σ ν = 2 poly ( 1/ ν ) and ρ η = 2 poly ( 1 / η ) \rho_\eta=2^{\operatorname{poly}(1/\eta)} ρ η = 2 poly ( 1/ η ) are the stretch factors of Theorems 2.2 and 2.5 ) with:
O ~ ( n ( 1 + ν + η ) / 2 ) \widetilde{O}(n^{(1+\nu+\eta)/2}) O ( n ( 1 + ν + η ) /2 ) amortized update time,
O ( ( m 0 + n ) n max { ν , η } ) O((m_0+n)n^{\max\{\nu,\eta\}}) O (( m 0 + n ) n m a x { ν , η } ) initialization time, and
O ( m t n max { ν , η } + n 1 + max { ν , η } ) O(m_t n^{\max\{\nu,\eta\}}+n^{1+\max\{\nu,\eta\}}) O ( m t n m a x { ν , η } + n 1 + m a x { ν , η } ) space, where m t m_t m t is the current number of edges.
After every update, cost queries take O ( 1 ) O(1) O ( 1 ) worst-case time, and reporting an explicit Steiner tree takes O ~ ( n 1 + ν ) \widetilde{O}(n^{1+\nu}) O ( n 1 + ν ) worst-case time.
Proof. Approximation for both the reported tree and the O ( 1 ) O(1) O ( 1 ) -time cost estimate ε c t \varepsilon c_t ε c t follows from Theorem 4.9 and Lemma 4.10. Initialization, amortized update, and worst-case reporting times follow from Lemma 4.11 and (14)–(15), and space follows from Lemma 4.12 .
In particular, for any fixed 0 < ζ < 1 / 2 0<\zeta<1/2 0 < ζ < 1/2 , choosing ν = η = ζ \nu=\eta=\zeta ν = η = ζ and ε = 1 / 2 \varepsilon=1/2 ε = 1/2 yields O ~ ( n 1 / 2 + ζ ) \widetilde{O}(n^{1/2+\zeta}) O ( n 1/2 + ζ ) amortized update time, O ( ( m 0 + n ) n ζ ) O((m_0+n)n^\zeta) O (( m 0 + n ) n ζ ) initialization time, O ( m t n ζ + n 1 + ζ ) O(m_t n^\zeta+n^{1+\zeta}) O ( m t n ζ + n 1 + ζ ) space, and O ~ ( n 1 + ζ ) \widetilde{O}(n^{1+\zeta}) O ( n 1 + ζ ) worst-case reporting time, proving Theorem 1.1 .
Remark 4.14 (Edge-weight changes). To update the weight of an edge u v uv uv , we simply delete u v uv uv and immediately reinsert it with its new weight before running the top-tree extraction and Mehlhorn reconnection in Update. Deleting u v uv uv first avoids creating parallel edges, and even if u v uv uv is a bridge so that the graph is momentarily disconnected between the two internal operations, the underlying spanner and HLS sparsifier support disconnected graphs without issue, while Mehlhorn’s reconnection on ( H t , Q t ) (H_t,Q_t) ( H t , Q t ) only runs once u v uv uv is back in place. In J t J_t J t , the deletion disables u v uv uv if it belonged to P 0 P_0 P 0 (so F t F_t F t never uses a stale phase-start weight) and enables its endpoint spokes u h , v h uh,vh u h , v h , while the insertion enables the owner spokes a ( u ) h , a ( v ) h a(u)h,a(v)h a ( u ) h , a ( v ) h to account for the new weight, increasing the per-update work and ∣ Z t ∣ , ∣ U t ∣ = O ( B ) |Z_t|,|U_t|=O(B) ∣ Z t ∣ , ∣ U t ∣ = O ( B ) by at most a constant factor.
Insertion-only Implementation and Analysis
This appendix provides the implementation details and analysis of the insertion-only algorithm in § 3 . We begin in Appendix § 6 .§ 1 with the maintenance of our Steiner augmentation structures: the distance and next-hop matrices of the auxiliary multigraph L F L_F L F on the endpoint set X X X , and the augmented terminal MST M \mathcal{M} M on T 0 ∪ C F T_0\cup C_F T 0 ∪ C F . We then establish the approximation guarantee in Appendix § 6 .§ 2 and analyze the running time and space usage in Appendix § 6 .§ 3 . For fixed integers s , r ≥ 2 s,r\ge2 s , r ≥ 2 and constant 0 < δ < 1 0<\delta<1 0 < δ < 1 , σ = ( 2 s − 1 ) ( 1 + δ ) \sigma=(2s-1)(1+\delta) σ = ( 2 s − 1 ) ( 1 + δ ) and A = 2 r − 1 A=2r-1 A = 2 r − 1 denote the spanner stretch (Theorem 2.1 ) and distance-oracle stretch (Theorem 2.3 ), respectively.
Implementation
At the start of each phase, the frozen structures on the spanner S S S are built directly using Theorems 2.8 and 2.3. Within a phase, processing each edge insertion consists of two steps: updating shortest-path distances in the auxiliary multigraph L F L_F L F on the endpoint set X X X , and propagating the resulting candidate-edge weight decreases to the augmented terminal MST M \mathcal{M} M on T 0 ∪ C F T_0\cup C_F T 0 ∪ C F .
Maintaining the auxiliary multigraph. Recall that L F L_F L F is the auxiliary multigraph on the endpoint set X X X , containing newly inserted edges in F F F and virtual edges supplied by the distance oracle on S S S . To maintain exact shortest-path distances in L F L_F L F while supporting path recovery in time proportional to the number of hops when reporting a Steiner tree, we maintain two matrices on the endpoint set X X X . For each pair i , j ∈ X i,j\in X i , j ∈ X , the distance matrix stores D F ( i , j ) = d L F ( i , j ) D_F(i,j)=d_{L_F}(i,j) D F ( i , j ) = d L F ( i , j ) (abbreviated D ( i , j ) D(i,j) D ( i , j ) below). For i ≠ j i\ne j i = j , the next-hop matrix Next ( i , j ) \operatorname{Next}(i,j) Next ( i , j ) stores the first edge i h ih ih of a shortest path from i i i to j j j , satisfying
D ( i , j ) = w ( i h ) + D ( h , j ) . (15) D(i,j)=w(ih)+D(h,j). \tag*{(15)} D ( i , j ) = w ( ih ) + D ( h , j ) . (15)
For identical endpoints, we set D ( i , i ) = 0 D(i,i)=0 D ( i , i ) = 0 and leave Next ( i , i ) \operatorname{Next}(i,i) Next ( i , i ) undefined. Since all edge weights are strictly positive and L F L_F L F is finite, no vertices are repeated and the recovered path must reach its destination.
Suppose an edge e = u v e=uv e = uv of weight c c c is inserted. It may introduce zero, one, or two new endpoints into X X X . We ensure that virtual edges connecting u u u and v v v to all existing vertices in X X X are in place before routes crossing e e e are evaluated by processing each new endpoint first. We compute its distances to existing endpoints in Step 1 and update distances among existing endpoints in Step 2, before inserting e e e in Step 3. Below, D − D_- D − and D + D_+ D + denote the distance matrices before and after each operation, respectively.
Distances involving a new endpoint. Let z z z be a new endpoint and X − X^- X − the endpoint set before adding it. We query and cache the distance estimates d ^ S ( z , x ) \widehat{d}_S(z,x) d S ( z , x ) for all x ∈ X − x\in X^- x ∈ X − , and add the
corresponding virtual edges to L F L_F L F . For each i ∈ X − i \in X^{-} i ∈ X − , we set
D + ( z , i ) = D + ( i , z ) = min x ∈ X − { d ^ S ( z , x ) + D − ( x , i ) } . (16) D_{+}(z,i)=D_{+}(i,z)=\min_{x\in X^{-}}\{\widehat{d}_S(z,x)+D_{-}(x,i)\}. \tag*{(16)} D + ( z , i ) = D + ( i , z ) = x ∈ X − min { d S ( z , x ) + D − ( x , i )} . (16)
Indeed, since z ∉ X − z \notin X^{-} z ∈ / X − and i ∈ X − i \in X^{-} i ∈ X − , any shortest z z z –i i i path in L F L_F L F must pass through at least one vertex in X − X^{-} X − . Let x ∈ X − x \in X^{-} x ∈ X − be the first vertex of X − X^{-} X − encountered along the path, splitting it into a z z z –x x x prefix and an x x x –i i i suffix. Because every edge inserted earlier has both endpoints in X − X^{-} X − , the z z z –x x x prefix cannot use any newly inserted edge. Thus, with no prior phase insertions affecting z z z –x x x , its L F L_F L F distance is given by the virtual edge weight d ^ S ( z , x ) \widehat{d}_S(z,x) d S ( z , x ) . Moreover, because x , i ∈ X − x,i \in X^{-} x , i ∈ X − and the x x x –i i i suffix does not revisit z z z , its corresponding distance on L F L_F L F is D − ( x , i ) D_{-}(x,i) D − ( x , i ) . Since x x x may be any vertex in X − X^{-} X − , minimizing d ^ S ( z , x ) + D − ( x , i ) \widehat{d}_S(z,x)+D_{-}(x,i) d S ( z , x ) + D − ( x , i ) over all x ∈ X − x \in X^{-} x ∈ X − gives the new distance D + ( z , i ) D_{+}(z,i) D + ( z , i ) on L F L_F L F , where x = i x=i x = i covers paths that reach i i i without visiting any other vertex in X − X^{-} X − since D − ( i , i ) = 0 D_{-}(i,i)=0 D − ( i , i ) = 0 . Finally, we set D + ( z , z ) = 0 D_{+}(z,z)=0 D + ( z , z ) = 0 .
If x ∈ X − x \in X^{-} x ∈ X − attains the minimum in (16) , we set Next + ( z , i ) \operatorname{Next}_{+}(z,i) Next + ( z , i ) to the virtual edge z x zx z x supplied by the distance oracle on S S S , and in the reverse direction we set Next + ( i , z ) \operatorname{Next}_{+}(i,z) Next + ( i , z ) to Next − ( i , x ) \operatorname{Next}_{-}(i,x) Next − ( i , x ) if x ≠ i x \ne i x = i and to the virtual edge i z iz i z otherwise. Since ∣ X − ∣ ≤ 2 B |X^{-}| \le2B ∣ X − ∣ ≤ 2 B and each distance-oracle query takes O ~ ( r ) \widetilde{O}(r) O ( r ) time, querying the O ( B ) O(B) O ( B ) distance estimates takes O ~ ( r B ) \widetilde{O}(rB) O ( r B ) time. Across all endpoints i ∈ X − i \in X^{-} i ∈ X − , evaluating the minimum in (16) takes O ( B 2 ) O(B^{2}) O ( B 2 ) time in total. Each corresponding next-hop entry takes constant time to set. Thus this step takes O ~ ( r B + B 2 ) \widetilde{O}(rB+B^{2}) O ( r B + B 2 ) time.
2) Distances between existing endpoints. Adding z z z may also shorten paths between vertices already in X − X^{-} X − . For every i , j ∈ X − i,j \in X^{-} i , j ∈ X − , we set
D + ( i , j ) = min { D − ( i , j ) , D + ( i , z ) + D + ( z , j ) } . (17) D_{+}(i,j)=\min\{D_{-}(i,j),D_{+}(i,z)+D_{+}(z,j)\}. \tag*{(17)} D + ( i , j ) = min { D − ( i , j ) , D + ( i , z ) + D + ( z , j )} . (17)
A shortest path either avoids z z z , in which case its best possible length is D − ( i , j ) D_{-}(i,j) D − ( i , j ) , or passes through z z z , in which case its length is D + ( i , z ) + D + ( z , j ) D_{+}(i,z)+D_{+}(z,j) D + ( i , z ) + D + ( z , j ) . The distances involving z z z were computed in the previous step. If the route through z z z is strictly cheaper, we set Next + ( i , j ) = Next + ( i , z ) \operatorname{Next}_{+}(i,j)=\operatorname{Next}_{+}(i,z) Next + ( i , j ) = Next + ( i , z ) , and otherwise we retain Next − ( i , j ) \operatorname{Next}_{-}(i,j) Next − ( i , j ) . This step takes O ( B 2 ) O(B^{2}) O ( B 2 ) time, since updating the distance and next-hop entries for each of the O ( B 2 ) O(B^{2}) O ( B 2 ) endpoint pairs takes constant time.
3) Inserting the edge. Once both endpoints are present, we insert e = u v e=uv e = uv with weight c c c and set, for every pair i , j ∈ X i,j \in X i , j ∈ X ,
D + ( i , j ) = min { D − ( i , j ) , D − ( i , u ) + c + D − ( v , j ) , D − ( i , v ) + c + D − ( u , j ) } . (18) D_{+}(i,j)=\min\{D_{-}(i,j),D_{-}(i,u)+c+D_{-}(v,j),D_{-}(i,v)+c+D_{-}(u,j)\}. \tag*{(18)} D + ( i , j ) = min { D − ( i , j ) , D − ( i , u ) + c + D − ( v , j ) , D − ( i , v ) + c + D − ( u , j )} . (18)
A shortest path either avoids e e e or crosses it in either direction. These are precisely the three expressions above. All entries on the right of (18) are read from the matrix obtained after introducing the endpoints but before inserting e e e .
We set Next + ( i , j ) = Next − ( i , j ) \operatorname{Next}_{+}(i,j)=\operatorname{Next}_{-}(i,j) Next + ( i , j ) = Next − ( i , j ) if the first expression in (18) achieves the minimum; if the second does, we set Next + ( i , j ) = Next − ( i , u ) \operatorname{Next}_{+}(i,j)=\operatorname{Next}_{-}(i,u) Next + ( i , j ) = Next − ( i , u ) when i ≠ u i \ne u i = u and Next + ( i , j ) = u v \operatorname{Next}_{+}(i,j)=uv Next + ( i , j ) = uv when i = u i=u i = u , and we apply the symmetric rule for the third expression (breaking ties in favor of the earliest expression in the displayed order of (18) ). Updating all O ( B 2 ) O(B^{2}) O ( B 2 ) endpoint pairs takes O ( B 2 ) O(B^{2}) O ( B 2 ) time, since evaluating the three expressions and setting the corresponding next-hop entry take constant time per pair.
Lemma A.1. With distance-oracle query time O ~ ( r ) \widetilde{O}(r) O ( r ) , processing one edge insertion maintains the exact distance and next-hop matrices of L F L_F L F in O ~ ( r B + B 2 ) \widetilde{O}(rB+B^{2}) O ( r B + B 2 ) time using O ( B 2 ) O(B^{2}) O ( B 2 ) space.
Proof. An insertion introduces at most two new endpoints to X X X . Summing the bounds from the three steps above gives total time O ~ ( r B + B 2 ) \widetilde{O}(rB+B^{2}) O ( r B + B 2 ) . The distance and next-hop matrices use O ( B 2 ) O(B^{2}) O ( B 2 ) space; keeping separate matrices for the values before and after each update does not change this bound. Storing L F L_F L F also takes O ( B 2 ) O(B^2) O ( B 2 ) space, since it contains at most B B B inserted edges and one virtual edge supplied by the distance oracle for each pair of endpoints in X X X , where ∣ X ∣ ≤ 2 B |X| \le2B ∣ X ∣ ≤ 2 B . Thus the total space is O ( B 2 ) O(B^2) O ( B 2 ) .
Maintaining the MST on T 0 ∪ C F T_0 \cup C_F T 0 ∪ C F
Once the updated distances D F ( x , y ) D_F(x,y) D F ( x , y ) in L F L_F L F are available, we propagate any improvements to the candidate edges C F C_F C F between terminal owners and update the maintained MST M \mathcal{M} M of T 0 ∪ C F T_0 \cup C_F T 0 ∪ C F . Since δ ( ⋅ ) \delta(\cdot) δ ( ⋅ ) is fixed during a phase and insertions only decrease D F ( x , y ) D_F(x,y) D F ( x , y ) , candidate weights c x y = δ ( x ) + D F ( x , y ) + δ ( y ) c_{xy} = \delta(x) + D_F(x,y) + \delta(y) c x y = δ ( x ) + D F ( x , y ) + δ ( y ) in (3) are monotonically non-increasing, which allows us to maintain M \mathcal{M} M via standard dynamic-tree edge replacements [ST81]. Specifically, for each unordered pair x , y ∈ X x,y \in X x , y ∈ X with distinct owners s = a ( x ) s = a(x) s = a ( x ) and t = a ( y ) t = a(y) t = a ( y ) , we evaluate c x y = δ ( x ) + D F ( x , y ) + δ ( y ) c_{xy} = \delta(x) + D_F(x,y) + \delta(y) c x y = δ ( x ) + D F ( x , y ) + δ ( y ) , adding the candidate edge to C F C_F C F if the pair is new or decreasing its weight otherwise. If a candidate edge with decreased weight already belongs to M \mathcal{M} M , we update its weight in M \mathcal{M} M directly; otherwise, we query the maximum-weight edge on the s s s –t t t path in M \mathcal{M} M and replace it with the candidate edge whenever the candidate edge is strictly lighter, maintaining the edge set of M \mathcal{M} M and its total weight w ( M ) w(\mathcal{M}) w ( M ) explicitly so that cost queries take O ( 1 ) O(1) O ( 1 ) worst-case time.
Lemma A.2. Maintaining the MST M \mathcal{M} M of T 0 ∪ C F T_0 \cup C_F T 0 ∪ C F in a link–cut tree [ST81] takes O ( ∣ R ∣ log n ) = O ~ ( n ) O(|R| \log n) = \widetilde{O}(n) O ( ∣ R ∣ log n ) = O ( n ) initialization time at the start of a phase, O ( B 2 log n ) = O ~ ( B 2 ) O(B^2 \log n) = \widetilde{O}(B^2) O ( B 2 log n ) = O ( B 2 ) amortized time per edge insertion within a phase, and O ( ∣ R ∣ + B 2 ) O(|R| + B^2) O ( ∣ R ∣ + B 2 ) space.
Proof. A link–cut tree supports finding a maximum-weight edge on a tree path, updating edge weights, and cutting and linking tree edges in O ( log n ) O(\log n) O ( log n ) amortized time per operation [ST81]. At the beginning of each phase, we initialize it with M = T 0 \mathcal{M} = T_0 M = T 0 by inserting the ∣ R ∣ − 1 |R| - 1 ∣ R ∣ − 1 tree edges using link operations in O ( ∣ R ∣ log n ) = O ~ ( n ) O(|R| \log n) = \widetilde{O}(n) O ( ∣ R ∣ log n ) = O ( n ) time. During the phase, each candidate-edge insertion or weight decrease requires at most one path-maximum query, one cut, and one link—only a constant number of link–cut tree operations—and therefore takes O ( log n ) O(\log n) O ( log n ) amortized time. Since there are O ( B 2 ) O(B^2) O ( B 2 ) endpoint pairs, maintaining M \mathcal{M} M takes O ( B 2 log n ) = O ~ ( B 2 ) O(B^2 \log n) = \widetilde{O}(B^2) O ( B 2 log n ) = O ( B 2 ) amortized time per edge insertion. The link–cut tree uses O ( ∣ R ∣ ) O(|R|) O ( ∣ R ∣ ) space. Together with T 0 T_0 T 0 and the O ( B 2 ) O(B^2) O ( B 2 ) candidate edges in C F C_F C F , MST maintenance uses O ( ∣ R ∣ + B 2 ) O(|R| + B^2) O ( ∣ R ∣ + B 2 ) space.
Approximation Analysis
We now show that M \mathcal{M} M provides a 2 σ A 2\sigma A 2 σ A -approximation throughout each phase. Let G ∘ G^\circ G ∘ be the graph at the beginning of the phase and F F F the set of edges inserted during the phase, so G = G ∘ ∪ F G = G^\circ\cup F G = G ∘ ∪ F is the current underlying graph. Define H F = K S ( R ) ∪ C F H_F = K_S(R) \cup C_F H F = K S ( R ) ∪ C F , where K S ( R ) K_S(R) K S ( R ) is the terminal metric closure of the frozen spanner snapshot S S S , and C F C_F C F contains the candidate edges maintained during the phase. Because any s s s –t t t shortest path in G G G that uses newly inserted edges in F F F must enter and leave the endpoint set X X X at some first and last vertices x , y ∈ X x,y \in X x , y ∈ X , its middle subpath between x x x and y y y can be approximated in L F L_F L F and lifted to terminals a ( x ) , a ( y ) ∈ R a(x),a(y) \in R a ( x ) , a ( y ) ∈ R via C F C_F C F , while its outer portions in G ∘ G^\circ G ∘ are approximated by K S ( R ) K_S(R) K S ( R ) . This gives the following terminal-distance comparison, where σ = ( 2 s − 1 ) ( 1 + δ ) \sigma= (2s - 1)(1 + \delta) σ = ( 2 s − 1 ) ( 1 + δ ) is the spanner stretch and A = 2 r − 1 A = 2r - 1 A = 2 r − 1 is the distance-oracle stretch.
Lemma A.3 (Terminal-distance comparison). For every pair of terminals s , t ∈ R s,t \in R s , t ∈ R ,
d G ( s , t ) ≤ d H F ( s , t ) ≤ σ A d G ( s , t ) . d_G(s,t) \le d_{H_F}(s,t) \le\sigma A d_G(s,t). d G ( s , t ) ≤ d H F ( s , t ) ≤ σ A d G ( s , t ) .
Proof. Every edge of K S ( R ) K_S(R) K S ( R ) corresponds to a walk in S ⊆ G S \subseteq G S ⊆ G of equal weight, and each candidate edge in C F C_F C F for an endpoint pair x , y x,y x , y represents a walk in G G G of no greater weight. The predecessor paths from a ( x ) a(x) a ( x ) to x x x and from y y y to a ( y ) a(y) a ( y ) have weights δ ( x ) \delta(x) δ ( x ) and δ ( y ) \delta(y) δ ( y ) , denoting the exact distances from x x x and y y y to their respective owners in S S S . Furthermore, any shortest x x x –y y y path in L F L_F L F expands—through direct edges and the path-reporting oracle—into a walk in G G G of weight at most D F ( x , y ) D_F(x,y) D F ( x , y ) . Combining these segments yields a total route weight of at most c x y = δ ( x ) + D F ( x , y ) + δ ( y ) c_{xy} = \delta(x) + D_F(x,y) + \delta(y) c x y = δ ( x ) + D F ( x , y ) + δ ( y ) . Consequently, every route in H F H_F H F admits a walk in G G G of no greater weight, establishing the lower bound.
For the upper bound, let P P P be a shortest s s s –t t t path in G G G . We consider two cases.
The path uses no edge inserted during the phase. Then P P P lies in G ∘ G^\circ G ∘ , and the metric edge s t st s t in K S ( R ) K_S(R) K S ( R ) has weight
d S ( s , t ) ≤ σ d G ∘ ( s , t ) = σ w ( P ) (spanner stretch, xref‘Theorem 2.1‘). d_S(s,t) \le\sigma d_{G^\circ}(s,t) = \sigma w(P) \qquad\text{(spanner stretch, {xref}`Theorem 2.1`).} d S ( s , t ) ≤ σ d G ∘ ( s , t ) = σ w ( P ) (spanner stretch, xref ‘Theorem 2.1‘).
The path uses at least one edge inserted during the phase. Let x x x and y y y be the first and last vertices of the endpoint set X X X encountered along P P P , respectively, which decomposes P P P as
P = P s ∘ P x y ∘ P t , P = P_s \circ P_{xy} \circ P_t, P = P s ∘ P x y ∘ P t ,
where P s P_s P s runs from s s s to x x x , P x y P_{xy} P x y from x x x to y y y , and P t P_t P t from y y y to t t t . Both outer portions contain only edges of G ∘ G^\circ G ∘ : an inserted edge there would have an endpoint in X X X before x x x or after y y y .
Let a = a ( x ) a = a(x) a = a ( x ) and b = a ( y ) b = a(y) b = a ( y ) , and consider the walk in H F H_F H F given by
s ⟶ a ⟶ b ⟶ t , s \longrightarrow a \longrightarrow b \longrightarrow t, s ⟶ a ⟶ b ⟶ t ,
where the first and last steps use metric edges of K S ( R ) K_S(R) K S ( R ) , while the middle step uses the candidate edge in C F C_F C F associated with x , y x,y x , y (omitting any step between identical terminals). The total weight is at most
d S ( s , a ) + δ ( x ) + D F ( x , y ) + δ ( y ) + d S ( b , t ) . d_S(s,a) + \delta(x) + D_F(x,y) + \delta(y) + d_S(b,t). d S ( s , a ) + δ ( x ) + D F ( x , y ) + δ ( y ) + d S ( b , t ) .
Eliminating any cycles yields a simple s s s –t t t path in H F H_F H F of no greater weight. We bound the three portions of the displayed expression separately.
For the left portion, since s s s is a terminal and a a a is the nearest terminal to x x x in S S S , we have δ ( x ) = d S ( a , x ) ≤ d S ( s , x ) \delta(x) = d_S(a,x) \le d_S(s,x) δ ( x ) = d S ( a , x ) ≤ d S ( s , x ) . By the triangle inequality, d S ( s , a ) ≤ d S ( s , x ) + d S ( x , a ) = d S ( s , x ) + δ ( x ) d_S(s,a) \le d_S(s,x) + d_S(x,a) = d_S(s,x) + \delta(x) d S ( s , a ) ≤ d S ( s , x ) + d S ( x , a ) = d S ( s , x ) + δ ( x ) . Therefore,
d S ( s , a ) + δ ( x ) ≤ d S ( s , x ) + 2 δ ( x ) (triangle inequality in S ) ≤ 3 d S ( s , x ) (nearest-terminal ownership, δ ( x ) ≤ d S ( s , x ) ) ≤ 3 σ w ( P s ) (spanner stretch on P s ⊆ G ∘ , Theorem 2.1). \begin{aligned}
d_S(s,a) + \delta(x) &\le d_S(s,x) + 2\delta(x) && \text{(triangle inequality in }S\text{)}\\
&\le3d_S(s,x) && \text{(nearest-terminal ownership, }\delta(x) \le d_S(s,x)\text{)}\\
&\le3\sigma w(P_s) && \text{(spanner stretch on }P_s \subseteq G^\circ\text{, Theorem 2.1).}
\end{aligned} d S ( s , a ) + δ ( x ) ≤ d S ( s , x ) + 2 δ ( x ) ≤ 3 d S ( s , x ) ≤ 3 σ w ( P s ) (triangle inequality in S ) (nearest-terminal ownership, δ ( x ) ≤ d S ( s , x ) ) (spanner stretch on P s ⊆ G ∘ , Theorem 2.1).
Symmetrically, the right portion satisfies
δ ( y ) + d S ( b , t ) ≤ 3 σ w ( P t ) . \delta(y) + d_S(b,t) \le3\sigma w(P_t). δ ( y ) + d S ( b , t ) ≤ 3 σ w ( P t ) .
For the middle portion, recall that D F ( x , y ) D_F(x,y) D F ( x , y ) is the exact shortest-path distance in L F L_F L F , whose edges are either newly inserted edges or virtual edges supplied by the distance oracle on S S S . The path P x y P_{xy} P x y may alternate arbitrarily between old and newly inserted edges. Retaining each newly inserted edge and replacing each consecutive group Q Q Q of old edges, with endpoints u , v u,v u , v , by the virtual edge u v ∈ E ( L F ) uv \in E(L_F) uv ∈ E ( L F ) (since u , v ∈ X u,v \in X u , v ∈ X ) gives
d ^ S ( u , v ) ≤ A d S ( u , v ) (oracle stretch, xref‘Theorem 2.3‘) ≤ A σ d G ∘ ( u , v ) ≤ A σ w ( Q ) (spanner stretch on Q ⊆ G ∘ , Theorem 2.1). \begin{aligned}
\widehat{d}_S(u,v) \le A d_S(u,v) \qquad\text{(oracle stretch, {xref}`Theorem 2.3`)} \\
&\le A\sigma d_{G^\circ}(u,v) \le A\sigma w(Q) \qquad\text{(spanner stretch on }Q \subseteq G^\circ\text{, Theorem 2.1).}
\end{aligned} d S ( u , v ) ≤ A d S ( u , v ) (oracle stretch, xref ‘Theorem 2.3‘) ≤ A σ d G ∘ ( u , v ) ≤ A σ w ( Q ) (spanner stretch on Q ⊆ G ∘ , Theorem 2.1).
Let ℓ o l d \ell_{\mathrm{old}} ℓ old and ℓ n e w \ell_{\mathrm{new}} ℓ new be the total weights of old and newly inserted edges in P x y P_{xy} P x y , respectively. These replacements give an x x x –y y y route in L F L_F L F of weight at most A σ ℓ o l d + ℓ n e w A\sigma\ell_{\mathrm{old}}+\ell_{\mathrm{new}} A σ ℓ old + ℓ new : replacing old-edge groups incurs a factor of at most A σ A\sigma A σ , while newly inserted edges are used directly in L F L_F L F with the same weights as in P x y P_{xy} P x y . As D F ( x , y ) D_F(x,y) D F ( x , y ) is the shortest distance in L F L_F L F , it is no greater than the weight of this route. Therefore,
D F ( x , y ) ≤ A σ w ( P x y ) . (19) D_F(x,y) \le A\sigma w(P_{xy}). \tag*{(19)} D F ( x , y ) ≤ A σ w ( P x y ) . (19)
Adding the bounds gives
d H F ( s , t ) ≤ 3 σ w ( P s ) + A σ w ( P x y ) + 3 σ w ( P t ) ≤ max { A , 3 } σ w ( P ) = A σ d G ( s , t ) \begin{aligned}
d_{H_F}(s,t) &\le3\sigma w(P_s) + A\sigma w(P_{xy}) + 3\sigma w(P_t) \\
&\le\max\{A,3\}\sigma w(P) = A\sigma d_G(s,t)
\end{aligned} d H F ( s , t ) ≤ 3 σ w ( P s ) + A σ w ( P x y ) + 3 σ w ( P t ) ≤ max { A , 3 } σ w ( P ) = A σ d G ( s , t )
(since A = 2 r − 1 ≥ 3 A=2r-1\ge3 A = 2 r − 1 ≥ 3 for r ≥ 2 r\ge2 r ≥ 2 and w ( P ) = d G ( s , t ) w(P)=d_G(s,t) w ( P ) = d G ( s , t ) ), which proves the upper bound.
Lemma A.3 shows that H F = K S ( R ) ∪ C F H_F=K_S(R)\cup C_F H F = K S ( R ) ∪ C F approximates pairwise terminal distances in G G G within a factor of σ A \sigma A σ A . Combining this distance comparison with the metric-MST bound bounds mst ( H F ) \operatorname{mst}(H_F) mst ( H F ) within 2 σ A OPT G ( R ) 2\sigma A\operatorname{OPT}_G(R) 2 σ A OPT G ( R ) , while the MST augmentation property ensures that M \mathcal{M} M achieves the same weight, i.e., w ( M ) = mst ( H F ) w(\mathcal{M})=\operatorname{mst}(H_F) w ( M ) = mst ( H F ) . Expanding the edges of M \mathcal{M} M into their underlying walks in G G G yields our 2 σ A 2\sigma A 2 σ A -approximate Steiner tree.
Theorem A.4. Expanding the edges of the maintained terminal MST M \mathcal{M} M into walks in G G G , taking their union, removing cycles, and pruning nonterminal leaves yields a Steiner tree T T T for R R R with
w ( T ) ≤ w ( M ) ≤ 2 σ A OPT G ( R ) . w(T) \le w(\mathcal{M}) \le2\sigma A\operatorname{OPT}_G(R). w ( T ) ≤ w ( M ) ≤ 2 σ A OPT G ( R ) . Since σ = ( 2 s − 1 ) ( 1 + δ ) \sigma=(2s-1)(1+\delta) σ = ( 2 s − 1 ) ( 1 + δ ) and A = 2 r − 1 A=2r-1 A = 2 r − 1 , we get approximation factor 2 ( 2 s − 1 ) ( 2 r − 1 ) ( 1 + δ ) 2(2s-1)(2r-1)(1+\delta) 2 ( 2 s − 1 ) ( 2 r − 1 ) ( 1 + δ ) .
Proof. Let M G M_G M G be an MST of the current terminal metric closure K G ( R ) K_G(R) K G ( R ) . For every edge s t ∈ M G st\in M_G s t ∈ M G , Lemma A.3 gives an s s s –t t t path P s t ′ P'_{st} P s t ′ in H F H_F H F of weight at most σ A d G ( s , t ) \sigma A d_G(s,t) σ A d G ( s , t ) . Their union connects all terminals and therefore contains a spanning tree of H F H_F H F . Consequently,
w ( M ) = mst ( T 0 ∪ C F ) = mst ( H F ) w(\mathcal{M})=\operatorname{mst}(T_0\cup C_F)=\operatorname{mst}(H_F) w ( M ) = mst ( T 0 ∪ C F ) = mst ( H F )
(MST augmentation, Lemma 2.10 )
≤ w ( ⋃ s t ∈ E ( M G ) P s t ′ ) ≤ ∑ s t ∈ E ( M G ) w ( P s t ′ ) \le w\left(\bigcup_{st\in E(M_G)}P'_{st}\right)\le\sum_{st\in E(M_G)}w(P'_{st}) ≤ w s t ∈ E ( M G ) ⋃ P s t ′ ≤ s t ∈ E ( M G ) ∑ w ( P s t ′ )
(the union counts shared edges at most once)
≤ σ A ∑ s t ∈ E ( M G ) d G ( s , t ) = σ A w ( M G ) \le\sigma A\sum_{st\in E(M_G)}d_G(s,t)=\sigma A w(M_G) ≤ σ A s t ∈ E ( M G ) ∑ d G ( s , t ) = σ A w ( M G )
(Lemma A.3)
≤ 2 σ A OPT G ( R ) \le2\sigma A\operatorname{OPT}_G(R) ≤ 2 σ A OPT G ( R )
(metric-MST bound, Lemma 2.6 ).
Finally, expanding the edges of M \mathcal{M} M into walks in G G G (and, for the selected candidate edges in E ( M ) ∩ C F E(\mathcal{M})\cap C_F E ( M ) ∩ C F , replacing the union of their shortest paths in L F L_F L F by a spanning forest on X X X before expanding virtual edges via the path-reporting oracle), taking their union, removing cycles, and pruning nonterminal leaves preserves terminal connectivity without increasing weight, yielding a Steiner tree T T T with
w ( T ) ≤ w ( M ) ≤ 2 σ A OPT G ( R ) . w(T)\le w(\mathcal{M})\le2\sigma A\operatorname{OPT}_G(R). w ( T ) ≤ w ( M ) ≤ 2 σ A OPT G ( R ) .
Time and Space Analysis
It remains to analyze the running time and space usage for fixed parameters s , r ≥ 2 s,r \ge2 s , r ≥ 2 and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) . We first establish the running time of each routine (initialization, phase reconstruction, single-update processing, and tree reporting) as a function of the phase length B B B , and then choose B B B to balance the update cost. The space usage is bounded in Lemma A.6 .
Lemma A.5. For fixed integers s , r ≥ 2 s,r \ge2 s , r ≥ 2 , constant δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , and phase length 1 ≤ B ≤ n 1 \le B \le n 1 ≤ B ≤ n , the procedures of the insertion-only algorithm satisfy the following time bounds:
(i) Initialization: O ~ ( m 0 + n 1 + 1 / s + 1 / r ) \widetilde{O}(m_0+n^{1+1/s+1/r}) O ( m 0 + n 1 + 1/ s + 1/ r ) expected time.
(ii) Phase reconstruction: O ~ ( n 1 + 1 / s + 1 / r / B + B ) \widetilde{O}\left(n^{1+1/s+1/r}/B+B\right) O ( n 1 + 1/ s + 1/ r / B + B ) expected amortized time per insertion over B B B insertions.
(iii) Single-update processing: O ~ ( B 2 ) \widetilde{O}(B^2) O ( B 2 ) expected amortized time per insertion.
(iv) Tree reporting: O ~ ( B n ) \widetilde{O}(Bn) O ( B n ) worst-case time per query.
Proof. We establish the four bounds in order.
Initialization. Before the first phase, initializing the dynamic spanner S 0 S_0 S 0 on m 0 m_0 m 0 edges takes O ~ ( n + m 0 ) \widetilde{O}(n+m_0) O ( n + m 0 ) expected time (Theorem 2.1 ). Performing the initial phase reconstruction on the snapshot S = S 0 S=S_0 S = S 0 (where E [ ∣ E ( S ) ∣ ] = O ~ ( n 1 + 1 / s ) \mathbb{E}[|E(S)|]=\widetilde{O}(n^{1+1/s}) E [ ∣ E ( S ) ∣ ] = O ( n 1 + 1/ s ) and L F , C F L_F,C_F L F , C F are initially empty) takes O ~ ( n 1 + 1 / s + 1 / r ) \widetilde{O}(n^{1+1/s+1/r}) O ( n 1 + 1/ s + 1/ r ) expected time as shown next, giving O ~ ( m 0 + n 1 + 1 / s + 1 / r ) \widetilde{O}(m_0+n^{1+1/s+1/r}) O ( m 0 + n 1 + 1/ s + 1/ r ) expected initialization time in total.
Phase reconstruction. Let m S = ∣ E ( S ) ∣ m_S=|E(S)| m S = ∣ E ( S ) ∣ be the number of edges in the frozen spanner snapshot S S S at the start of a phase, where m S ≥ n − 1 m_S \ge n-1 m S ≥ n − 1 because S S S is connected and E [ m S ] = O ~ ( n 1 + 1 / s ) \mathbb{E}[m_S]=\widetilde{O}(n^{1+1/s}) E [ m S ] = O ( n 1 + 1/ s ) by Theorem 2.1 . Copying S S S and running Mehlhorn’s construction to obtain the owner forest and terminal-metric MST T 0 T_0 T 0 takes O ~ ( m S + n ) \widetilde{O}(m_S+n) O ( m S + n ) deterministic time (Theorem 2.8 ), building the path-reporting distance oracle on S S S takes O ~ ( m S n 1 / r ) \widetilde{O}(m_S n^{1/r}) O ( m S n 1/ r ) expected time (Theorem 2.3 ), initializing the link–cut tree with M = T 0 \mathcal{M}=T_0 M = T 0 takes O ~ ( n ) \widetilde{O}(n) O ( n ) deterministic time (Lemma A.2), and clearing the O ( B 2 ) O(B^2) O ( B 2 ) entries of L F L_F L F and C F C_F C F takes O ( B 2 ) O(B^2) O ( B 2 ) deterministic time. Taking expectations over m S m_S m S and the randomized oracle construction gives expected reconstruction time
O ~ ( E [ m S ] + n + E [ m S ] n 1 / r + B 2 ) = O ~ ( n 1 + 1 / s + 1 / r + B 2 ) . \widetilde{O}\left(\mathbb{E}[m_S]+n+\mathbb{E}[m_S]n^{1/r}+B^2\right)=\widetilde{O}\left(n^{1+1/s+1/r}+B^2\right). O ( E [ m S ] + n + E [ m S ] n 1/ r + B 2 ) = O ( n 1 + 1/ s + 1/ r + B 2 ) .
Charging each reconstruction after the first to the B B B insertions of the preceding phase gives
O ~ ( n 1 + 1 / s + 1 / r B + B ) (20) \widetilde{O}\left(\frac{n^{1+1/s+1/r}}{B}+B\right) \tag*{(20)} O ( B n 1 + 1/ s + 1/ r + B ) (20)
expected amortized time per insertion.
Single-update processing. On each edge insertion, updating the dynamic spanner S t S_t S t takes O ~ ( 1 ) \widetilde{O}(1) O ( 1 ) expected amortized time (Theorem 2.1 ), updating the distance and next-hop matrices of L F L_F L F takes O ~ ( r B + B 2 ) = O ~ ( B 2 ) \widetilde{O}(rB+B^2)=\widetilde{O}(B^2) O ( r B + B 2 ) = O ( B 2 ) deterministic time (Lemma A.1 ), and maintaining the augmented terminal MST M \mathcal{M} M on T 0 ∪ C F T_0 \cup C_F T 0 ∪ C F takes O ~ ( B 2 ) \widetilde{O}(B^2) O ( B 2 ) deterministic amortized time (Lemma A.2). Summing these costs gives expected amortized single-update time O ~ ( B 2 ) \widetilde{O}(B^2) O ( B 2 ) .
Tree reporting. To materialize an explicit Steiner tree on query, we first partition the ∣ R ∣ − 1 |R|-1 ∣ R ∣ − 1 edges of M \mathcal{M} M into E ( M ) ∩ E ( T 0 ) E(\mathcal{M}) \cap E(T_0) E ( M ) ∩ E ( T 0 ) and E ( M ) ∩ C F E(\mathcal{M}) \cap C_F E ( M ) ∩ C F in O ( ∣ R ∣ ) = O ( n ) O(|R|)=O(n) O ( ∣ R ∣ ) = O ( n ) time. Because every candidate edge in C F C_F C F connects two terminals in the active owner set A F = { a ( x ) : x ∈ X } ⊆ R A_F=\{a(x):x\in X\}\subseteq R A F = { a ( x ) : x ∈ X } ⊆ R of size ∣ A F ∣ ≤ ∣ X ∣ ≤ 2 B |A_F|\le|X|\le2B ∣ A F ∣ ≤ ∣ X ∣ ≤ 2 B and M \mathcal{M} M is acyclic, the subgraph E ( M ) ∩ C F E(\mathcal{M})\cap C_F E ( M ) ∩ C F is a forest on A F A_F A F and therefore contains at most ∣ A F ∣ − 1 < 2 B |A_F|-1<2B ∣ A F ∣ − 1 < 2 B candidate edges. Next, we include the stored cross-region edges in S S S for E ( M ) ∩ E ( T 0 ) E(\mathcal{M})\cap E(T_0) E ( M ) ∩ E ( T 0 ) and coherently expand all required owner-forest routes—both from the cross-region endpoints of E ( M ) ∩ E ( T 0 ) E(\mathcal{M})\cap E(T_0) E ( M ) ∩ E ( T 0 ) and from the endpoints x , y ∈ X x,y\in X x , y ∈ X associated with E ( M ) ∩ C F E(\mathcal{M})\cap C_F E ( M ) ∩ C F —by walking up the rooted owner forest in S S S , marking visited vertices and stopping each walk upon reaching a terminal root or an already marked vertex (as in Lemma 2.9 ). This traverses each of the at most n − 1 n-1 n − 1 owner-forest edges at most once, taking O ( n ) O(n) O ( n ) time and contributing O ( n ) O(n) O ( n ) edges. For each of the fewer than 2 B 2B 2 B candidate edges in E ( M ) ∩ C F E(\mathcal{M})\cap C_F E ( M ) ∩ C F with endpoint pair ( x , y ) ∈ X 2 (x,y)\in X^2 ( x , y ) ∈ X 2 , we recover a shortest x x x –y y y path P x y P_{xy} P x y in L F L_F L F of at most ∣ X ∣ − 1 < 2 B |X|-1<2B ∣ X ∣ − 1 < 2 B hops via Next in O ( B 2 ) O(B^2) O ( B 2 ) total time, and extract a spanning forest F L ⊆ ⋃ P x y F_L\subseteq\bigcup P_{xy} F L ⊆ ⋃ P x y on X X X in O ( B 2 ) O(B^2) O ( B 2 ) time. Since F L F_L F L is a forest on X X X , it connects every such pair ( x , y ) (x,y) ( x , y ) with weight w L F ( F L ) ≤ ∑ D F ( x , y ) w_{L_F}(F_L)\le\sum D_F(x,y) w L F ( F L ) ≤ ∑ D F ( x , y ) and contains at most ∣ X ∣ − 1 < 2 B |X|-1<2B ∣ X ∣ − 1 < 2 B edges of L F L_F L F . Each edge of F L F_L F L is either a newly inserted edge in F F F or a virtual edge expanded into a simple path P P P in S S S of at most n − 1 n-1 n − 1 edges by the path-reporting oracle in O ~ ( r + ∣ E ( P ) ∣ ) = O ~ ( n ) \widetilde{O}(r+|E(P)|)=\widetilde{O}(n) O ( r + ∣ E ( P ) ∣ ) = O ( n ) time (Theorem 2.3 ), so expanding F L F_L F L requires fewer than 2 B 2B 2 B oracle queries and produces O ( B n ) O(Bn) O ( B n ) edge occurrences in O ~ ( B n ) \widetilde{O}(Bn) O ( B n ) time. Finally, removing cycles and pruning non-terminal leaves across the O ( B n ) O(Bn) O ( B n ) collected edges takes O ( B n ) O(Bn) O ( B n ) time, giving O ~ ( B n ) \widetilde{O}(Bn) O ( B n ) worst-case reporting time.
Combining the single-update cost with the amortized phase-reconstruction cost shows that any sequence of U ≥ 1 U\ge1 U ≥ 1 insertions takes O ~ ( U B 2 + ⌊ U / B ⌋ n 1 + 1 / s + 1 / r ) \widetilde{O}(UB^2+\lfloor U/B\rfloor n^{1+1/s+1/r}) O ( U B 2 + ⌊ U / B ⌋ n 1 + 1/ s + 1/ r ) expected time beyond initialization, corresponding to an expected amortized update time of
T u p d ( B ) = O ~ ( n 1 + 1 / s + 1 / r B + B ) + O ~ ( B 2 ) = O ~ ( n 1 + 1 / s + 1 / r B + B 2 ) . (21) T_{\mathrm{upd}}(B)=\widetilde{O}\left(\frac{n^{1+1/s+1/r}}{B}+B\right)+\widetilde{O}(B^2)=\widetilde{O}\left(\frac{n^{1+1/s+1/r}}{B}+B^2\right). \tag*{(21)} T upd ( B ) = O ( B n 1 + 1/ s + 1/ r + B ) + O ( B 2 ) = O ( B n 1 + 1/ s + 1/ r + B 2 ) . (21)
Choosing B = ⌈ n ( 1 + 1 / s + 1 / r ) / 3 ⌉ B=\left\lceil n^{(1+1/s+1/r)/3}\right\rceil B = ⌈ n ( 1 + 1/ s + 1/ r ) /3 ⌉ yields expected amortized update time T u p d = O ~ ( n 2 3 ( 1 + 1 / s + 1 / r ) ) T_{\mathrm{upd}}=\widetilde{O}\left(n^{\frac{2}{3}(1+1/s+1/r)}\right) T upd = O ( n 3 2 ( 1 + 1/ s + 1/ r ) ) , and tree-reporting time O ~ ( B n ) = O ~ ( n 4 / 3 + ( 1 / s + 1 / r ) / 3 ) \widetilde{O}(Bn)=\widetilde{O}\left(n^{4/3+(1/s+1/r)/3}\right) O ( B n ) = O ( n 4/3 + ( 1/ s + 1/ r ) /3 ) .
Lemma A.6. Let m t = ∣ E ( G t ) ∣ m_t=|E(G_t)| m t = ∣ E ( G t ) ∣ be the current edge count. For fixed integers s , r ≥ 2 s,r\ge2 s , r ≥ 2 with 1 / s , 1 / r ≤ 1 / 2 1/s,1/r\le1/2 1/ s , 1/ r ≤ 1/2 and our choice of B B B , the total expected space used is
O ~ ( m t + n 1 + 1 / min { s , r } ) . \widetilde{O}\left(m_t+n^{1+1/\min\{s,r\}}\right). O ( m t + n 1 + 1/ m i n { s , r } ) .
Proof. Storing the current graph takes O ( m t + n ) O(m_t+n) O ( m t + n ) space; maintaining the dynamic spanner S t S_t S t and its frozen snapshot S S S takes O ~ ( n 1 + 1 / s ) \widetilde{O}(n^{1+1/s}) O ( n 1 + 1/ s ) expected space (Theorem 2.1 ); storing the path-reporting distance oracle on S S S takes O ~ ( n 1 + 1 / r ) \widetilde{O}(n^{1+1/r}) O ( n 1 + 1/ r ) expected space (Theorem 2.3 ); and storing the owner forest and T 0 T_0 T 0 takes O ( n ) O(n) O ( n ) space (Theorem 2.8 ). Within a phase, maintaining L F L_F L F takes O ( B 2 ) O(B^2) O ( B 2 ) space (Lemma A.1 ) and maintaining M \mathcal{M} M on T 0 ∪ C F T_0\cup C_F T 0 ∪ C F takes O ( ∣ R ∣ + B 2 ) O(|R|+B^2) O ( ∣ R ∣ + B 2 ) space (Lemma A.2). Summing these bounds and using ∣ R ∣ ≤ n |R|\le n ∣ R ∣ ≤ n gives total expected space
O ~ ( m t + n 1 + 1 / s + n 1 + 1 / r + B 2 ) . \widetilde{O}\left(m_t+n^{1+1/s}+n^{1+1/r}+B^2\right). O ( m t + n 1 + 1/ s + n 1 + 1/ r + B 2 ) .
For B = ⌈ n ( 1 + 1 / s + 1 / r ) / 3 ⌉ B=\lceil n^{(1+1/s+1/r)/3}\rceil B = ⌈ n ( 1 + 1/ s + 1/ r ) /3 ⌉ and a = max { 1 / s , 1 / r } = 1 / min { s , r } ≤ 1 / 2 a=\max\{1/s,1/r\}=1/\min\{s,r\}\le1/2 a = max { 1/ s , 1/ r } = 1/ min { s , r } ≤ 1/2 , we have 2 3 ( 1 + 1 / s + 1 / r ) ≤ 2 3 ( 1 + 2 a ) ≤ 1 + a \frac{2}{3}(1+1/s+1/r)\le\frac{2}{3}(1+2a)\le1+a 3 2 ( 1 + 1/ s + 1/ r ) ≤ 3 2 ( 1 + 2 a ) ≤ 1 + a , so B 2 = O ( n 1 + a ) B^2=O(n^{1+a}) B 2 = O ( n 1 + a ) is absorbed by O ~ ( n 1 + 1 / s + n 1 + 1 / r ) = O ~ ( n 1 + 1 / min { s , r } ) \widetilde{O}(n^{1+1/s}+n^{1+1/r})=\widetilde{O}(n^{1+1/\min\{s,r\}}) O ( n 1 + 1/ s + n 1 + 1/ r ) = O ( n 1 + 1/ m i n { s , r } ) .
Combining Theorem A.4 with Lemmas A.5 and A.6 yields the full parameterized guarantee for our insertion-only data structure.
Theorem A.7 (Parameterized version of Theorem 1.2 ). Let G G G be a connected n n n -vertex incremental undirected graph with m 0 m_0 m 0 edges initially, a terminal set R R R , and polynomially bounded positive edge weights over all updates. For any fixed integers s , r ≥ 2 s,r \ge2 s , r ≥ 2 and constant 0 < δ < 1 0 < \delta< 1 0 < δ < 1 , setting phase length B = ⌈ n ( 1 + 1 / s + 1 / r ) / 3 ⌉ B = \lceil n^{(1+1/s+1/r)/3}\rceil B = ⌈ n ( 1 + 1/ s + 1/ r ) /3 ⌉ gives a randomized insertion-only data structure against an oblivious adversary that maintains a 2 ( 2 s − 1 ) ( 2 r − 1 ) ( 1 + δ ) 2(2s-1)(2r-1)(1+\delta) 2 ( 2 s − 1 ) ( 2 r − 1 ) ( 1 + δ ) -approximate Steiner tree for R R R in G G G with:
O ~ ( n 2 / 3 + ( 1 + 1 / s + 1 / r ) ) \widetilde{O}\left(n^{2/3+(1+1/s+1/r)}\right) O ( n 2/3 + ( 1 + 1/ s + 1/ r ) ) expected amortized update time,
O ~ ( m 0 + n 1 + 1 / s + 1 / r ) \widetilde{O}\left(m_0+n^{1+1/s+1/r}\right) O ( m 0 + n 1 + 1/ s + 1/ r ) expected initialization time, and
O ~ ( m t + n 1 + 1 / min { s , r } ) \widetilde{O}\left(m_t+n^{1+1/\min\{s,r\}}\right) O ( m t + n 1 + 1/ m i n { s , r } ) expected space, where m t m_t m t is the current number of edges.
After every insertion, the approximation guarantee holds deterministically, cost queries take O ( 1 ) O(1) O ( 1 ) worst-case time, and reporting an explicit Steiner tree takes O ~ ( n 4 / 3 + ( 1 / s + 1 / r ) / 3 ) \widetilde{O}\left(n^{4/3+(1/s+1/r)/3}\right) O ( n 4/3 + ( 1/ s + 1/ r ) /3 ) worst-case time.
Proof. Approximation follows from Theorem A.4 , returning the maintained scalar weight w ( M ) w(\mathcal{M}) w ( M ) on cost queries in O ( 1 ) O(1) O ( 1 ) worst-case time. Initialization, amortized update, and worst-case reporting times follow from Lemma A.5 and (21) (since 1 ≤ B = ⌈ n ( 1 + 1 / s + 1 / r ) / 3 ⌉ ≤ ⌈ n 2 / 3 ⌉ ≤ n 1 \le B = \lceil n^{(1+1/s+1/r)/3}\rceil\le\lceil n^{2/3}\rceil\le n 1 ≤ B = ⌈ n ( 1 + 1/ s + 1/ r ) /3 ⌉ ≤ ⌈ n 2/3 ⌉ ≤ n for all s , r ≥ 2 s,r \ge2 s , r ≥ 2 and n ≥ 1 n \ge1 n ≥ 1 ), and expected space follows from Lemma A.6 .
In particular, for any fixed 0 < ζ < 1 / 3 0 < \zeta< 1/3 0 < ζ < 1/3 , choosing s = r = ⌈ 2 / ζ ⌉ s=r=\lceil2/\zeta\rceil s = r = ⌈ 2/ ζ ⌉ gives 1 / s = 1 / r ≤ ζ / 2 1/s=1/r \le\zeta/2 1/ s = 1/ r ≤ ζ /2 and ( 2 s − 1 ) ( 2 r − 1 ) = O ( 1 / ζ 2 ) (2s-1)(2r-1)=O(1/\zeta^2) ( 2 s − 1 ) ( 2 r − 1 ) = O ( 1/ ζ 2 ) , establishing Theorem 1.2 (with update time O ~ ( n 2 / 3 + 2 ζ / 3 ) \widetilde{O}(n^{2/3+2\zeta/3}) O ( n 2/3 + 2 ζ /3 ) , space O ~ ( m t + n 1 + ζ / 2 ) \widetilde{O}(m_t+n^{1+\zeta/2}) O ( m t + n 1 + ζ /2 ) , and reporting time O ~ ( n 4 / 3 + ζ / 3 ) \widetilde{O}(n^{4/3+\zeta/3}) O ( n 4/3 + ζ /3 ) ). Choosing s = r = 5 s=r=5 s = r = 5 , δ = ε / 162 \delta=\varepsilon/162 δ = ε /162 , and B = ⌈ n 7 / 15 ⌉ B=\lceil n^{7/15}\rceil B = ⌈ n 7/15 ⌉ yields a ( 162 + ε ) (162+\varepsilon) ( 162 + ε ) -approximation in O ~ ( n 14 / 15 ) \widetilde{O}(n^{14/15}) O ( n 14/15 ) expected amortized update time. □ \square □
AI Use Statement
We used GPT-5.6-Sol to learn about the problem and explore candidate constructions. While the main ideas behind the constructions and abstractions are our own, GPT-5.6-Sol was invaluable in exploring proof approaches and in formalizing proof sketches. The authors verified the correctness and originality of all content, including references.
References
[1 ] Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry , 9(1):81–100, 1993.
[2 ] Giorgio Ausiello, Camil Demetrescu, Paolo Giulio Franciosa, Giuseppe F. Italiano, and Andrea Ribichini. Small stretch spanners in the streaming model: New algorithms and experiments. In Proceedings of the 15th Annual European Symposium on Algorithms (ESA) , volume 4698 of Lecture Notes in Computer Science , pages 605–617, 2007.
[3 ] Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Transactions on Algorithms , 1(2):243–264, 2005.
[4 ] Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS) , pages 184–193, 1996.