betaFeedback

WorksComputer Science

Tight Bounds for Sublinear Metric Steiner Tree

Abstract

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

Introduction

The Steiner tree problem asks for a minimum-weight network connecting a prescribed set of terminals, possibly through additional points. It is one of Karp’s original NP-complete problems [26]; the best known polynomial-time approximation ratio is ln⁡4+ε≈1.39\ln4+\varepsilon\approx1.39 [6], and no ratio better than 96/9596/95 is achievable unless P=NP\mathrm{P}=\mathrm{NP} [13]. Steiner problems have also been studied in streaming [14], dynamic [25, 24, 29], online [25, 23, 1, 3, 4], and sublinear-query models [16, 31].

An instance of the metric Steiner tree problem consists of a finite set VV of nn points, a metric ww on VV, and a set T⊆VT\subseteq V of kk terminals. A feasible solution is a tree in the complete graph on VV whose vertex set contains TT; we write OPT\mathrm{OPT} for the least weight of a feasible solution. In the distance-oracle model an algorithm knows VV and TT and may query any pair {u,v}\{u,v\} to learn w(u,v)w(u,v); its cost is the number of queries. Let LL be the weight of a minimum spanning tree (MST) of the metric restricted to TT. Doubling a Steiner tree and shortcutting gives OPT≤L≤2OPT\mathrm{OPT}\leq L\leq2\mathrm{OPT}, and Czumaj and Sohler [19] showed that LL can be estimated within a factor 1+ε1+\varepsilon using O~(k)\widetilde{O}(k) queries, so a (2+ε)(2+\varepsilon)-estimate needs only a nearly linear number of queries. The natural question that prior works have focused on is the cost of estimating OPT\mathrm{OPT} within a factor strictly below 22.

Chen, Khanna, and Tan [16] initiated this study and settled much of the landscape: estimating OPT\mathrm{OPT} within a factor 5/3−ε5/3-\varepsilon requires Ωε(n2)\Omega_\varepsilon(n^2) queries, even when k=O(1)k=O(1), and explicitly returning a tree of weight below 2⋅OPT2\cdot\mathrm{OPT} requires Ω(nk)\Omega(nk) queries. This explains why we can only aim for estimation algorithms (that do not return a tree). They also gave an estimator with a factor 2−ε02-\varepsilon_0 using O~(n12/7+kn6/7)=O~(n13/7)\widetilde{O}(n^{12/7}+kn^{6/7})=\widetilde{O}(n^{13/7}) queries. Mahabadi, Roghani, Tarnawski, and Vakilian [31] improved this to O~(n5/3)\widetilde{O}(n^{5/3}) using improved bounds for sublinear set cover. On the lower-bound side, [16] showed that Ω~(n+k6/5)\widetilde{\Omega}(n+k^{6/5}) queries are needed, which is Ω~(n6/5)\widetilde{\Omega}(n^{6/5}) when k=Θ(n)k=\Theta(n). Mahabadi, Tarnawski, and Vakilian [33] then gave an improved lower bound of Ω~(n7/5)\widetilde{\Omega}(n^{7/5}). See also Table 1.

TaskLower boundUpper boundReference
Estimation within 2+ε2+\varepsilonΩ(k)\Omega(k)O~(k)\widetilde{O}(k)[19]
Estimation within 2−ε2-\varepsilonΩ~(n+k6/5)\widetilde{\Omega}(n+k^{6/5})O~(n13/7)\widetilde{O}(n^{13/7})[16]
O~(n5/3)\widetilde{O}(n^{5/3})[31]
Ω~(n7/5)\widetilde{\Omega}(n^{7/5})[33]
this paperΩε,ε′(n3/2−ε′)\Omega_{\varepsilon,\varepsilon'}(n^{3/2-\varepsilon'})O~(n3/2)\widetilde{O}(n^{3/2})Theorems 1.1 and 1.2
Estimation within 53−ε\frac{5}{3}-\varepsilonΩε(n2)\Omega_{\varepsilon}(n^2)O(n2)O(n^2)[16]
Return a tree of weight ≤(2−ε)OPT\le(2-\varepsilon)\mathrm{OPT}Ω(nk)\Omega(nk)O(nk)O(nk)[16]

Table 1. Bounds for metric Steiner tree in the distance-oracle model. The upper bounds below factor 2 hold for one particular (very small) constant ε0>0\varepsilon_0>0; our lower bound holds for every fixed ε∈(0,1)\varepsilon\in(0,1) and every fixed ε′>0\varepsilon'>0, and the instances have k=Θ(n)k=\Theta(n).

This problem belongs to a broader line of work on estimating optimization problems with distance or adjacency queries, including minimum spanning tree [18, 19], maximal independent set [34, 36, 32], matching [36, 27, 5, 9, 11, 10, 7, 30, 2], Steiner forest [32], and metric TSP [15, 17].

Our results

We determine the exponent of the query complexity of estimation below factor 22. Following [16, 31], we define an estimate within factor 2−η2-\eta to be a number C^\widehat{C} with

OPT≤C^≤(2−η)OPT.(1)\mathrm{OPT}\leq\widehat{C}\leq(2-\eta)\mathrm{OPT}. \tag*{(1)}

Theorem 1.1 (Upper bound). There is an absolute constant η0>0\eta_0>0 and a randomized algorithm that, given an nn-point instance, outputs with probability at least 2/32/3 a number C^\widehat{C} satisfying (1) with η=η0\eta=\eta_0. In the worst case it makes O~(n3/2)\widetilde{O}(n^{3/2}) distance queries and uses O~(n3/2)\widetilde{O}(n^{3/2}) time.

We also show that the exponent 3/23/2 is tight by giving an improved hardness for sublinear algorithms. See Corollary 1.3.

Theorem 1.2 (Lower bound). For every η∈(0,1)\eta\in(0,1) and every integer s≥1s\geq1 there are constants cη,s>0c_{\eta,s}>0 and nη,sn_{\eta,s} such that the following holds for every n≥nη,sn\geq n_{\eta,s}. Every randomized algorithm that, on every nn-point instance, outputs with probability at least 2/32/3 a number C^\widehat{C} satisfying (1) makes at least cη,snbsc_{\eta,s}n^{b_s} queries in expectation on some instance, where

bs=3s+72s+5=32−14s+10.b_s=\frac{3s+7}{2s+5}=\frac{3}{2}-\frac{1}{4s+10}.

The hard instances have Θη,s(n)\Theta_{\eta,s}(n) terminals, and every distance between two distinct points lies in {Θη,s(n−3),1,2}\{\Theta_{\eta,s}(n^{-3}),1,2\}.

Corollary 1.3. For every fixed η∈(0,1)\eta\in(0,1) and ε>0\varepsilon>0, estimating the metric Steiner tree cost within a factor 2−η2-\eta requires Ωη,ε(n3/2−ε)\Omega_{\eta,\varepsilon}(n^{3/2-\varepsilon}) queries. In particular, for the factor 2−η02-\eta_0 of Theorem 1.1 the query complexity is n3/2±o(1)n^{3/2\pm o(1)}.

The n3/2n^{3/2} query complexity is thus tight up to subpolynomial factors. The lower bound is stated for expected query complexity; in particular it also holds for worst-case complexity.

Lean formalization Both of our results are formalized in Lean. The formalization is available under https://github.com/vakiliana/sublinear-steiner-tree.

In the following § 1.2 and § 1.3 we give an intuitive overview of the techniques underlying our results.

Technical Overview of the Algorithm

In this section, we provide an overview of the techniques used to design our algorithm of Theorem 1.1. We begin with the framework of Chen, Khanna, and Tan [16] and its implementation by Mahabadi, Roghani, Tarnawski, and Vakilian [31], which reduces estimation below factor 2 to estimating a set cover quantity and estimates that quantity by estimating the size of a maximal matching in an auxiliary graph. We then describe the new idea that brings the cost of this set cover step from O~(n5/3)\widetilde{O}(n^{5/3}) down to O~(n3/2)\widetilde{O}(n^{3/2}). As we will see, this idea alone does not yield an O~(n3/2)\widetilde{O}(n^{3/2}) algorithm for Steiner tree, and we describe the remaining challenges and how we overcome them step by step. Throughout, nn is the number of points, k≤nk\le n the number of terminals, and for simplicity we assume k=Θ(n)k=\Theta(n), which is the hardest case. A nonterminal point is called a center.

Overview of the Previous Algorithms

Starting point: the terminal MST and the set cover reduction. Let LL be the weight of a minimum spanning tree on the terminals. It is well known that OPT≤L≤2OPT\mathrm{OPT}\le L\le2\mathrm{OPT}, and LL can be estimated within a factor 1+ε1+\varepsilon using O~(k)\widetilde{O}(k) queries [19]. Therefore the whole difficulty of beating factor 2 is to certify, with few queries, a discount D≤L−OPTD\le L-\mathrm{OPT} that is a constant fraction of LL whenever such a discount exists. The algorithm then outputs L−DL-D. The framework of [16] looks for two types of improvements over the MST. For the first type, fix a scale aa and consider the clusters of terminals at this scale, i.e., the connected components of the graph on terminals in which two terminals are adjacent if their distance is less than aa. The MST spends roughly aa to connect each of these clusters to the rest. Now, if a center vv is close to three or more clusters, we can instead connect all of them to vv using short edges, which is cheaper. For the second type, we look for a small group of terminals (at most four) inside one cluster that can be connected through a single center more cheaply than the MST connects them. The main structural result of [16] is that these two types of improvements are the only ones that matter: if neither type yields a significant improvement at any scale, then L≤(2−η)OPT⁡L \le(2-\eta)\operatorname{OPT}, and it suffices to output an estimate of LL.

The first type of improvement is naturally a set cover problem. Fix a scale aa and let the universe UU be the set of clusters at scale aa. For each center vv, let Sv⊆US_v \subseteq U be the clusters that have a terminal within distance 5a/85a/8 of vv. A set SvS_v is useful only if ∣Sv∣≥3|S_v| \ge3, since connecting two clusters through a center is never cheaper than connecting them directly. We call such sets eligible (see Figure 1(a)). Let F\mathcal{F} be the collection of all sets SvS_v, and write SC⁡(U,F)\operatorname{SC}(U,\mathcal{F}) for the least number of eligible sets and singletons needed to cover UU. The total improvement of the first type at scale aa is captured by the saving

References

  1. [1][AAB96] Baruch Awerbuch, Yossi Azar, and Yair Bartal. On-line generalized Steiner problem. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 68–74, 1996.
  2. [2][ABRR25] Amir Azarmehr, Soheil Behneshzad, Mohammad Roghani, and Aviad Rubinstein. Tight pair query lower bounds for matching and earth mover’s distance. In 66th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 2666–2693, 2025.arxiv.org/abs/2510.16351
  3. [3][BC97] Piotr Berman and Chris Coulston. On-line algorithms for Steiner tree problems. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC), pages 344–353, 1997.
  4. [4][BDM22] Etienne Bamas, Marina Drygala, and Andreas Maggiori. An improved analysis of greedy for online Steiner forest. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3202–3229, 2022.arxiv.org/abs/2111.10086
  5. [5][Beh21] Soheil Behnnezhad. Time-optimal sublinear algorithms for matching and vertex cover. In 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 873–884, 2021.
  6. [6][BGRS13] Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. Journal of the ACM, 60(1):6:1–6:33, 2013. Preliminary version in STOC 2010.DOI
  7. [7][BKS23] Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. Sublinear algorithms for (1.5 + ε)-approximate matching. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pages 254–266, 2023.
  8. [8][BNS+16] Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC), pages 1046–1059, 2016.
  9. [9]Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Sublinear time algorithms and complexity of approximate maximum matching. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pages 267–280, 2023.
  10. [10]Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Approximating maximum matching requires almost quadratic time. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 444–454, 2024.
  11. [11]Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, and Amin Saberi. Beating greedy matching in sublinear time. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3900–3945, 2023.
  12. [12]Lucien Le Cam. Convergence of estimates under dimensionality restrictions. The Annals of Statistics, 1(1):38–53, 1973.
  13. [13]Miroslav Chlebík and Janka Chlebíková. The Steiner tree problem on graphs: Inapproximability results. Theoretical Computer Science, 406(3):207–214, 2008.DOI
  14. [14]Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Streaming algorithms for geometric Steiner forest. In 49th International Colloquium on Automata, Languages, and Programming (ICALP), volume 229 of LIPIcs, pages 47:1–47:20, 2022.
  15. [15]Yu Chen, Sampath Kannan, and Sanjeev Khanna. Sublinear algorithms and lower bounds for metric TSP cost estimation. In 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168 of LIPIcs, pages 30:1–30:19, 2020.arxiv.org/abs/2006.05490
  16. [16]Yu Chen, Sanjeev Khanna, and Zihan Tan. Query complexity of the metric Steiner tree problem. In Proceedings of the 2023 Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 4893–4935, 2023. Full version: arXiv:2211.03893.arxiv.org/abs/2211.03893
  17. [17]Yu Chen, Sanjeev Khanna, and Zihan Tan. Sublinear algorithms and lower bounds for estimating MST and TSP cost in general metrics. In 50th International Colloquium on Automata, Languages, and Programming (ICALP), volume 261 of LIPIcs, pages 37:1–37:16, 2023.arxiv.org/abs/2203.14798
  18. [18]Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM Journal on Computing, 34(6):1370–1379, 2005.
  19. [19]Artur Czumaj and Christian Sohler. Estimating the weight of metric minimum spanning trees in sublinear time. SIAM Journal on Computing, 39(3):904–922, 2009.
  20. [20]Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-Interscience, Hoboken, NJ, second edition, 2006.
  21. [21]Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC), pages 117–126, 2015.arxiv.org/abs/1411.2664
  22. [22]Manuela Fischer and Andreas Noever. Tight analysis of parallel randomized greedy MIS. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2152–2160, 2018. Full version: arXiv:1707.05124.arxiv.org/abs/1707.05124
  23. [23]Albert Gu, Anupam Gupta, and Amit Kumar. The power of deferral: Maintaining a constant-competitive Steiner tree online. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (STOC), pages 525–534, 2013.
  24. [24]Anupam Gupta and Amit Kumar. Online Steiner tree with deletions. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 455–467, 2014.arxiv.org/abs/1312.7296
  25. [25]Makoto Imase and Bernard M. Waxman. Dynamic Steiner tree problem. SIAM Journal on Discrete Mathematics, 4(3):369–384, 1991.DOI
  26. [26]Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Complexity of Computer Computations, pages 85–103. Plenum Press, New York, 1972.
  27. [27]Michael Kapralov, Slobodan Mitrović, Ashkan Norouzi-Fard, and Jakab Tardos. Space efficient approximation to maximum matching size from uniform edge samples. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1753–1772, 2020.arxiv.org/abs/1907.05725
  28. [28]Haim Kaplan, Yishay Mansour, and Uri Stemmer. The sparse vector technique, revisited. In Proceedings of the 34th Conference on Learning Theory (COLT), volume 134 of Proceedings of Machine Learning Research, 2021. arXiv:2010.00917.arxiv.org/abs/2010.00917
  29. [29]Jakub Łącki, Jakub Oćwieja, Marcin Pilipczuk, Piotr Sankowski, and Anna Zych. The power of dynamic distance oracles: Efficient dynamic algorithms for the Steiner tree. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC), pages 11–20, 2015.
  30. [30]Sepideh Mahabadi, Mohammad Roghani, and Jakub Tarnawski. A 0.51-approximation of maximum matching in sublinear n^1.5 time. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP), volume 334 of LIPIcs, pages 116:1–116:17, 2025.arxiv.org/abs/2506.01669
  31. [31]Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, and Ali Vakilian. Sublinear metric Steiner tree via improved bounds for set cover. In 16th Innovations in Theoretical Computer Science Conference (ITCS), volume 325 of LIPIcs, pages 74:1–74:24, 2025.arxiv.org/abs/2411.09059
  32. [32]Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, and Ali Vakilian. Sublinear metric Steiner forest via maximal independent set. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5941–5959, 2026.
  33. [33]Sepideh Mahabadi, Jakub Tarnawski, and Ali Vakilian. A better lower bound for sublinear metric Steiner tree. In 18th Innovations in Theoretical Computer Science Conference (ITCS), LIPIcs, 2027. To appear. Full version: arXiv:2610.41666.arxiv.org/abs/2610.41666
  34. [34]Huy N. Nguyen and Krzysztof Onak. Constant-time approximation algorithms via local improvements. In 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 327–336, 2008.DOI
  35. [35]Yihong Wu and Pengkun Yang. Chebyshev polynomials, moment matching, and optimal estimation of the unseen. The Annals of Statistics, 47(2):857–883, 2019.arxiv.org/abs/1504.01227
  36. [36]Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. An improved constant-time approximation algorithm for maximum matchings. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing (STOC), pages 225–234, 2009.DOI

Paper details

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

views · 6

downloads · 0

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

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents