Query Complexity of the Metric Steiner Tree Problem

In the metric Steiner Tree problem, we are given an n × n metric w on a set V of vertices along with a set T ⊆ V of k terminals, and the goal is to find a tree of minimum cost that contains all terminals in T. This is a well-known NP-hard problem and much of the previous work has focused on understanding its polynomial-time approximability. In this work, we initiate a study of the query complexity of the metric Steiner Tree problem. Specifically, if we desire an α-approximate estimate of the metric Steiner Tree cost, how many entries need to be queried in the metric w? For the related minimum spanning tree (MST) problem, this question is well-understood. For any fixed ε > 0, one can estimate the MST cost to within a (1 + ε)-factor using only Õ(n) queries, and this is known to be essentially tight. Can one obtain a similar result for Steiner Tree cost? Note that a (2 + ε)-approximate estimate of Steiner Tree cost can be obtained with Õ(k) queries by simply applying the MST cost estimation algorithm on the metric induced by the terminals. Our first result shows that the Steiner Tree problem behaves in a fundamentally different manner from MST: any (randomized) algorithm that estimates the Steiner Tree cost to within a (5/3 − ε)-factor requires Ω(n²) queries, even if k is a constant. This lower bound is in sharp contrast to an upper bound of O(nk) queries for computing a (5/3)-approximate Steiner Tree, which follows from previous work by Du and Zelikovsky. Our second main result, and the main technical contribution of this work, is a sublinear query algorithm for estimating the Steiner Tree cost to within a strictly better-than-2 factor. We give an algorithm that achieves this goal, with a query complexity of (Equation presented); since k ≤ n, the algorithm performs at most (Equation presented) queries in the worst-case. Our estimation algorithm reduces this task to that of designing a sublinear query algorithm for a suitable set cover problem. We complement this result by showing an (Equation presented) query lower bound for any algorithm that estimates Steiner Tree cost to a strictly better than 2 factor. Thus (Equation presented) queries are needed to just beat 2-approximation when k = Ω(n); a sharp contrast to MST cost estimation where a (1 + o(1))-approximate estimate of cost is achievable with only Õ(n) queries.