betaFeedback

WorksComputer Science

Dynamic Steiner Tree under Edge Updates

Abstract

The Steiner tree problem is the canonical generalization of minimum spanning tree (MST). When connectivity is required only among a fixed subset of vertices (terminals), the goal is to maintain a minimum-cost tree connecting these terminals as the graph undergoes edge updates. While dynamic MST has been studied since the 1980s~[Frederickson, STOC'83, SICOMP'85], and the first sublinear-in-nn dynamic MST algorithm dates back almost thirty-five years to Eppstein, Galil, Italiano, and Nissenzweig~[FOCS'92, JACM'97], achieving sublinear-in-nn update time for dynamic Steiner tree has long remained open, as a single edge update can invalidate many routes in the underlying terminal metric closure. We present the first fully dynamic algorithm for Steiner tree that achieves a constant-factor approximation with sublinear-in-nn update time. For any fixed 0<ζ<1/20<ζ<1/2, our deterministic algorithm maintains an Oζ(1)O_ζ(1)-approximate Steiner tree for undirected graphs with polynomially bounded edge weights in O~(n1/2+ζ)\widetilde O(n^{1/2+ζ}) amortized update time, answering cost queries in O(1)O(1) time, and reporting an explicit tree in O~(n1+ζ)\widetilde O(n^{1+ζ}) time. Our approach combines periodic terminal-metric rebuilds on a dynamic spanner with a top-tree dynamic program that localizes edge deletions and reconnects surviving components through a dynamic distance sparsifier. Along the way, we give a simpler randomized insertion-only algorithm with a better, explicit approximation ratio.

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+nlog⁡n)O(m+n \log n) time [Meh88]. Zelikovsky later improved the approximation factor to 11/611/6 [Zel93], and subsequent work reduced it further to 1.7461.746 [BR94], 5/3+ε5/3+\varepsilon [PS00], 1.6441.644 [KZ97], and 1.5981.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)-approximation of Byrka et al. [BGRS13] for any fixed ε>0\varepsilon>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}) worst-case update bound for maintaining an MST in an nn-vertex mm-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) time. To overcome graph density, Eppstein, Galil, Italiano, and Nissenzweig developed sparsification trees to obtain the first bound sublinear in nn [EGIN92, EGIN97]. Later, Holm, de Lichtenberg, and Thorup combined Euler tour trees with hierarchical edge levels to achieve O(log⁡4n)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)-approximate Steiner tree in general weighted graphs with sublinear-in-nn 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(n1.529+k2n1+o(1))O(n^{1.529}+k^2n^{1+o(1)}) update time, where kk 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) 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) time has remained unresolved.

Our Contribution. We give a strong affirmative answer to the question above.

Theorem 1.1. Let GG be a connected nn-vertex fully dynamic undirected graph with m0m_0 edges initially, a terminal set RR, and polynomially bounded edge weights over all updates. For every fixed 0<ζ<1/20 < \zeta< 1/2, there is a deterministic fully dynamic algorithm that maintains an Oζ(1)O_{\zeta}(1)-approximate Steiner tree for RR in GG with O~(n1/2+ζ)\widetilde{O}(n^{1/2+\zeta}) amortized update time and O((m0+n)nζ)O((m_0+n)n^{\zeta}) initialization time. After every update, cost queries take O(1)O(1) time, and reporting the Steiner tree takes O~(n1+ζ)\widetilde{O}(n^{1+\zeta}) time.

Ours is the first fully dynamic algorithm that maintains a constant-factor approximate Steiner tree in sublinear-in-nn 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~(n1+ζ)\widetilde{O}(n^{1+\zeta}) 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) 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 GG be a connected nn-vertex incremental undirected graph with m0m_0 edges initially, a terminal set RR, and polynomially bounded edge weights over all updates. For every fixed 0<ζ<1/30 < \zeta< 1/3, there is a randomized insertion-only algorithm that maintains an O(1/ζ2)O(1/\zeta^2)-approximate Steiner tree for RR in GG with O~(n2/3+ζ)\widetilde{O}(n^{2/3+\zeta}) expected amortized update time and O~(m0+n1+ζ)\widetilde{O}(m_0+n^{1+\zeta}) expected initialization time. After every insertion, the approximation guarantee holds deterministically, cost queries take O(1)O(1) time, and reporting the Steiner tree takes O~(n4/3+ζ)\widetilde{O}(n^{4/3+\zeta}) time.

In particular, we can get a (162+ε)(162+\varepsilon)-approximation in O~(n14/15)\widetilde{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-nn 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 GG and terminal set RR of size k=∣R∣k = |R|, consider the complete graph on the terminals denoted by KG(R)K_G(R), with each edge weighted by its shortest-path distance dG(u,v)d_G(u,v) in the underlying graph. An MST of this terminal metric closure KG(R)K_G(R) expands into a Steiner tree of at most twice the optimum weight OPT⁡G(R)\operatorname{OPT}_G(R) [KMB81], cf. Lemma 2.6. To avoid constructing the Θ(k2)\Theta(k^2)-edge clique KG(R)K_G(R) explicitly, Mehlhorn [Meh88] runs a single multi-source Dijkstra computation from RR to partition VV into Voronoi regions around each vertex’s nearest terminal a(x)∈Ra(x) \in R at distance δ(x)=dG(a(x),x)\delta(x) = d_G(a(x),x), contracts each region into its terminal root so that every cross-region edge xyxy induces a candidate edge between a(x)a(x) and a(y)a(y) of weight δ(x)+w(xy)+δ(y)\delta(x) + w(xy) + \delta(y), and computes an MST of this sparse candidate graph in O(m+nlog⁡n)O(m + n \log n) time, cf. Theorem 2.8. Maintaining this construction under edge updates to GtG_t, however, presents significant algorithmic challenges. First, a single insertion or deletion can alter shortest-path distances across Θ(k2)\Theta(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 (k2)\binom{k}{2} terminal pairs reconstructs a ρ\rho-approximate terminal metric on RR. An MST of this graph estimates OPT⁡Gt(R)\operatorname{OPT}_{G_t}(R) within a 2ρ2\rho factor using O~(k2)\widetilde{O}(k^2) distance queries. Plugging in the deterministic dynamic distance oracle of Haeupler, Long, and Saranurak (HLS) [HLS24], which for any fixed 0<η<10 < \eta< 1 achieves stretch ρη=2poly⁡(1/η)\rho_\eta= 2^{\operatorname{poly}(1/\eta)}, we get O(nη)O(n^\eta) worst-case update time and an O(ρη)O(\rho_\eta)-approximate cost query in O~(k2)\widetilde{O}(k^2) time, since each distance query takes Oη(log⁡log⁡n)O_\eta(\log\log n) time.

To avoid querying all pairs, we can maintain a dynamic vertex sparsifier HtH_t on the terminal set RR that preserves pairwise distances within stretch ρ\rho, satisfying dGt(u,v)≤dHt(u,v)≤ρdGt(u,v)d_{G_t}(u,v) \le d_{H_t}(u,v) \le\rho d_{G_t}(u,v) for all u,v∈Ru,v \in R. Running Mehlhorn’s linear-time terminal-MST construction directly on (Ht,R)(H_t,R) computes an MST of KHt(R)K_{H_t}(R) in O~(∣V(Ht)∣+∣E(Ht)∣)\widetilde{O}(|V(H_t)|+|E(H_t)|) time, again yielding a 2ρ2\rho-approximate solution. Using the HLS vertex sparsifier [HLS24], we can maintain HtH_t of size O(knη)O(kn^\eta) in O(nη)O(n^\eta) amortized update time, reducing the cost-query time to O~(knη)\widetilde{O}(kn^\eta).

Both reductions support inexpensive O(nη)O(n^\eta)-time updates to their distance structure, but computing a fresh Steiner cost still requires an MST computation, incurring O~(k2)\widetilde{O}(k^2) or O~(knη)\widetilde{O}(kn^\eta) time. Moreover, neither structure supports outputting an explicit Steiner tree in GtG_t directly.

Spanners and Mehlhorn’s construction. A second approach is to use a dynamic σ\sigma-spanner St⊆GtS_t \subseteq G_t, which is a sparse subgraph satisfying dGt(u,v)≤dSt(u,v)≤σdGt(u,v)d_{G_t}(u,v) \le d_{S_t}(u,v) \le\sigma d_{G_t}(u,v) for all vertex pairs. Because StS_t is an actual subgraph of GtG_t, running Mehlhorn’s construction on (St,R)(S_t,R) yields an explicit 2σ2\sigma-approximate Steiner tree in O~(∣E(St)∣+n)\widetilde{O}(|E(S_t)|+n) time.

Using the deterministic dynamic spanner of Chuzhoy and Parter [CP25], which for any fixed 0<ν<10 < \nu< 1 achieves worst-case size O(n1+ν)O(n^{1+\nu}) and stretch σν=2poly⁡(1/ν)\sigma_\nu= 2^{\operatorname{poly}(1/\nu)} in O(nν)O(n^\nu) amortized update time, gives O(nν)O(n^\nu) update time and O~(n1+ν)\widetilde{O}(n^{1+\nu}) query time. The main drawback of this approach is that every query requires re-running Mehlhorn’s algorithm across all O(n1+ν)O(n^{1+\nu}) 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~(n1+ζ)\widetilde{O}(n^{1+\zeta}) 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 TT with V(Gt)⊆V(T)V(G_t) \subseteq V(T) satisfying dGt(u,v)≤dT(u,v)d_{G_t}(u,v) \le d_T(u,v) for all u,vu,v and expected stretch E[dT(u,v)]≤αdGt(u,v)\mathbb{E}[d_T(u,v)] \le\alpha d_{G_t}(u,v) as GtG_t undergoes edge updates. On a single tree TT, the minimum-weight subgraph connecting RR is simply the unique minimal subtree spanning RR, of weight CC. Doubling this subtree and shortcutting between consecutive terminals yields a tour in KGt(R)K_{G_t}(R) of weight at most 2C2C, so noncontraction implies OPT⁡Gt(R)≤2C\operatorname{OPT}_{G_t}(R) \le2C, while routing an optimal Steiner tree of GtG_t through TT gives E[C]≤αOPT⁡Gt(R)\mathbb{E}[C] \le\alpha\operatorname{OPT}_{G_t}(R) by linearity of expectation. Augmenting this embedding with top trees [3] allows us to maintain the weight CC of the minimal subtree spanning RR, with O(log⁡n)O(\log n) overhead per change to the embedding, making the 2α2\alpha-approximate cost estimate 2C2C available in O(1)O(1) query time after every update.

References

  1. [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.DOI
  2. [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. [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.DOI
  4. [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.

Paper details

vlnc:W_hqebmycj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 4

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-5.6 Sol (bare)

View statement
Looking for related papers…
Contents