Tight Bounds for Sublinear Metric Steiner Tree

In the metric Steiner tree problem we are given an n-point metric space $(V,w)$ and a set T⊆ V of terminals, and we seek the smallest weight OPT of a tree that spans T and may use points of V 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 OPT while querying significantly fewer than n² distances. The minimum spanning tree on T estimates OPT within a factor $2$, and its weight can be approximated with O(n) queries. The natural question that has been studied is therefore the query complexity of estimating OPT within a factor strictly below $2$. Chen, Khanna, and Tan [SODA 2023] gave such an algorithm using O(n13/7) queries, and a lower bound of Ω(n6/5). Later Mahabadi, Roghani, Tarnawski, and Vakilian [ITCS 2025] improved the algorithm to O(n5/3), and Mahabadi, Tarnawski, and Vakilian [ITCS 2027] improved the lower bound to Ω(n7/5). In this work we settle the above question. We give an algorithm that estimates OPT within a factor 2-η₀, for an absolute constant η₀>0, with query (and time) complexity O(n3/2). We also show that the exponent $3/2$ is tight.