CS Paper Radar

Dynamic Steiner Tree under Edge Updates

Jeff Giliberti, MohammadTaghi Hajiaghayi, Mohammad Mahdavi, Xinchen Yang

cs.DS ·submitted 2026-11-03 08:32 UTC · v1
hot direction

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-$n$ dynamic MST algorithm dates back almost thirty-five years to Eppstein, Galil, Italiano, and Nissenzweig~[FOCS'92, JACM'97], achieving sublinear-in-$n$ 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-$n$ update time. For any fixed $0<ζ<1/2$, our deterministic algorithm maintains an $O_ζ(1)$-approximate Steiner tree for undirected graphs with polynomially bounded edge weights in $\widetilde O(n^{1/2+ζ})$ amortized update time, answering cost queries in $O(1)$ time, and reporting an explicit tree in $\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.

Closest papers

Nearest neighbours by meaning across the whole index.

Steiner Tree Parameterized by Multiway Cut: Single-Exponential Time and Polynomial Space

cs.DS ·2026-10-30 ·Lukas Van de Voorde, Brecht Verbeken, Vincent Ginis
similarity 0.75
Abstract · 8 pages, 1 figure

In the Steiner Tree problem, the goal is to find a minimum-weight tree containing a given set of terminals in an edge-weighted graph. Given a multiway cut of size $s$, we propose a deterministic algorithm running in $2^{O(s)}\operatorname{poly}(n,b)$ time and polynomial space ($n$ vertices, non-negative $b$-bit integer weights). A multiway cut for the terminals is a set of vertices whose deletion leaves at most one terminal in each connected component. This result answers a question of Jansen and Swennenhuis (ESA 2024). Building on their component decomposition, we show that it suffices to connect the selected cut vertices together with $O(s)$ additional terminals and attach the remaining terminals by shortest paths. We use colour coding to optimize over the choice of these additional terminals.

0.25

Pairwise Reconnection for Cost-Distance Steiner Trees

cs.DS ·2026-11-06 ·Edgar Perner
theory similarity 0.74
Abstract

The Uniform Cost-Distance Steiner Tree Problem asks for a rooted tree that minimizes the connection cost plus a weighted sum of root-to-terminal distances. We develop an algorithm that constructs two candidate trees: one based on direct connections to the root and another that pairs selected vertices and connects each pair to the root. The algorithm selects the tree with the smaller objective value. The resulting randomized algorithm achieves expected approximation factors of $1.698$ in the spanning case and $2.041$ in the general case, and it can be derandomized in polynomial time. The pairwise matching analysis charges part of the augmentation cost directly to the connection and delay costs of an optimal solution, rather than only to the separated lower bound used in previous analyses. This allows the $1.698$ factor to fall below the maximum multiplicative gap of $1+1/\sqrt{2}$ between the optimum value and that lower bound. We give instance families with approximation-ratio lower bounds approaching $1+1/\sqrt{2}$ for cut-and-reconnect algorithms that start from a minimum spanning tree and $3/2$ for the present algorithm. Finally, we show that the Uniform Cost-Distance Steiner Tree Problem and the Steiner-tree version of the Cable-Trench Problem are approximation equivalent up to an arbitrarily small additive loss.

0.20

Tight Bounds for Sublinear Metric Steiner Tree

cs.DS ·2026-11-09 ·Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian
theory similarity 0.74
Abstract

In the metric Steiner tree problem we are given an $n$-point metric space $(V,w)$ and a set $T\subseteq V$ of terminals, and we seek the smallest weight $\mathrm{OPT}$ of a tree that spans $T$ and may use points of $V\setminus T$. We study sublinear algorithms in the distance-oracle model, where the algorithm knows $V$ and $T$ upfront and can query the distance function $w$. The objective is to estimate $\mathrm{OPT}$ while querying significantly fewer than $n^2$ distances. The minimum spanning tree on $T$ estimates $\mathrm{OPT}$ within a factor $2$, and its weight can be approximated with $\widetilde{O}(n)$ queries. The natural question that has been studied is therefore the query complexity of estimating $\mathrm{OPT}$ within a factor strictly below $2$. Chen, Khanna, and Tan [SODA 2023] gave such an algorithm using $\widetilde{O}(n^{13/7})$ queries, and a lower bound of $\widetildeΩ(n^{6/5})$. Later Mahabadi, Roghani, Tarnawski, and Vakilian [ITCS 2025] improved the algorithm to $\widetilde{O}(n^{5/3})$, and Mahabadi, Tarnawski, and Vakilian [ITCS 2027] improved the lower bound to $\widetildeΩ(n^{7/5})$. In this work we settle the above question. We give an algorithm that estimates $\mathrm{OPT}$ within a factor $2-η_0$, for an absolute constant $η_0>0$, with query (and time) complexity $\widetilde{O}(n^{3/2})$. We also show that the exponent $3/2$ is tight.

0.12

A Better Lower Bound for Sublinear Metric Steiner Tree

cs.DS ·2026-10-30 ·Sepideh Mahabadi, Jakub Tarnawski, Ali Vakilian
theory similarity 0.73
Abstract

In the metric Steiner tree problem, we are given an $n$-point metric space $(V,w)$ and a set of terminals $T\subseteq V$, and we are interested in the smallest total weight $\mathsf{st}(V,T,w)$ of a tree that contains every terminal and may also use points of $V\setminus T$. We work in the distance-oracle model: the algorithm knows $V$ and $T$ in advance and learns $w$ only by querying a single entry $w(u,v)$ at a time. The goal is to estimate $\mathsf{st}(V,T,w)$ with the minimum number of queries. A factor of $2$ is achievable with nearly linear number of queries, so the interesting question is the query complexity of algorithms with an approximation ratio strictly below $2$. We prove that for every fixed $η\in(0,1)$, every randomized $(2-η)$-approximation algorithm must make more than $\widetildeΩ(n^{7/5})$ queries, improving upon the previously known bound of $\widetildeΩ(n^{6/5})$. Given that the best known upper bound shows that $\widetilde O(n^{5/3})$ queries suffice, the exponent of this problem now lies between $7/5$ and $5/3$, up to logarithmic factors.

0.20

Dynamic Connectivity, Minimum Spanning Tree, and 2-Edge Connectivity with Polylogarithmic Worst-Case Update Time

cs.DS ·2026-09-30 ·Simon Meierhans, Maximilian Probst Gutenberg, Yu-Cheng Yeh
top venue similarity 0.73
Abstract · To appear in FOCS 2026

We give fully dynamic algorithms for maintaining connectivity, minimum spanning tree, and $2$-edge connectivity of a graph with worst-case polylogarithmic update time. Our algorithms are randomized and succeed with high probability against an adaptive adversary. For the minimum spanning tree and $2$-edge connectivity problems, this improves over the subpolynomial update time bounds obtained by Nanongkai, Saranurak, and Wulff-Nilsen [FOCS'17], Jin and Sun [FOCS'21], and Jin, Sun, and Thorup [SODA'24], respectively. The only randomized component of our algorithms is the computation of static expander decompositions, and a deterministic algorithm for said problem would directly imply deterministic algorithms for all three problems. This reduction is novel even for the connectivity problem.

0.24

Improved Lower Bound for Steiner Point Removal

cs.DS ·2026-09-16 ·Karthekeyan Chandrasekaran, Chandra Chekuri, Qingyun Chen, Weihao Zhu
theory similarity 0.70
Abstract

In the Steiner Point Removal problem, we are given a graph $G=(V,E)$ with an edge-length function $\ell_G: E\rightarrow \mathbb{R}_+$ and a subset $T\subseteq V$ of terminals. The goal is to find a minor $H=(T, E_H)$ of $G$ on vertex set $T$ such that the shortest path metric derived from $G$ on the edges of $H$ preserves the distance between every pair of terminals within a small multiplicative stretch. Filtser proved that a stretch of $O(\log |T|)$ can be achieved (in polynomial time), while Chen and Tan more recently proved a lower bound of $Ω\left(\sqrt{\frac{\log |T|}{\log\log |T|}}\right)$ on the achievable stretch. Their lower bound is via a simple construction involving low-degree high-girth graphs. The existence of such graphs is guaranteed through the existence of low-degree high-girth expanders. In this work, we improve the lower bound to $Ω(\sqrt{\log |T|})$ using the same simple construction of Chen and Tan but with a more careful analysis that exploits the expansion property.

0.18

Incremental Minimum Spanning Trees on a Napkin

cs.DS ·2026-11-03 ·Lucian Bicsi, Adrian Budău
similarity 0.68
Abstract · 20 pages, 5 figures, 3 tables

In the incremental minimum spanning forest problem, weighted edges arrive one at a time. After each insertion we must report the edge that leaves the minimum spanning forest, and queries ask for the bottleneck distance of two vertices: the smallest possible maximum edge cost on a path between them. Link-cut trees solve both in $O(\log n)$ amortized time. In 2021 we wrote the folklore BottleneckTree, a short competitive-programming structure that stores one parent pointer and one cost per vertex, and conjectured that it also runs in $O(\log n)$ amortized time. We show that this conjecture is false: on a family of inputs, its amortized cost per operation is $Ω(\sqrt{n})$. We then present a structure with the same state, two arrays and a single loop, and prove that it runs in $O(\log n)$ amortized time per insertion and per query. Unlike the AM-tree of Ding, Gu and Sun, which attains the same bound, it stores no subtree sizes and maintains no balance invariant. For a connected graph with distinct costs, the structure can be viewed as an implicit link-cut tree on the Kruskal reconstruction tree: each rotation corresponds to exactly one preferred-child change, and each skip acts on a stale path-parent pointer. In experiments it is 1.3-2.1 times faster than the folklore BottleneckTree on insertions, up to 480 times faster on its adversarial input, and 6.3-16 times faster than an explicit link-cut tree.

0.32

Improved Sublinear Algorithms for Maximal Independent Set and Metric Steiner Forest

cs.DS ·2026-10-05 ·Sepideh Mahabadi, Jakub Tarnawski
similarity 0.68
Abstract

In this work we consider the Maximal Independent Set (MIS) problem and the metric Steiner Forest problem in the sublinear time setting, under the adjacency/distance matrix query model. First, we give an algorithm that estimates the size of an MIS up to a multiplicative factor of $(1+\eps)$ using $\tO(n^{4/3}/\eps^2)$ queries. This improves the best previous algorithm by Mahabadi, Roghani, Tarnawski, and Vakilian (SODA 2026), which had a query complexity of $\tO(n^{3/2}/\eps^2)$. Via a reduction from that work, this would automatically imply the same improvement for the problem of estimating the metric Steiner Forest cost up to an $O(\log n)$ factor. However, as our second contribution, we consider the Steiner Forest problem directly and provide an algorithm with $\tO(n)$ query complexity that is very simple and does not proceed via MIS.

0.43