Sublinear Metric Steiner Tree via Improved Bounds for Set Cover

We study the metric Steiner tree problem in the sublinear query model. In this problem, for a set of n points V in a metric space given to us by means of query access to an n×n matrix w, and a set of terminals T⊆V, the goal is to find the minimum-weight subset of the edges that connects all the terminal vertices.
Recently, Chen, Khanna and Tan [SODA’23] gave an algorithm that uses Õ(n^(13/7)) queries and outputs a (2−η)-estimate of the metric Steiner tree weight, where η>0 is a universal constant. A key component in their algorithm is a sublinear algorithm for a particular set cover problem where, given a set system (U,F), the goal is to provide a multiplicative-additive estimate for |U|−SC(U,F). Here U is the set of elements, F is the collection of sets, and SC(U,F) denotes the optimal set cover size of (U,F). In particular, their algorithm returns a (1/4,ε⋅|U|)-multiplicative-additive estimate for this set cover problem using Õ(|F|^(7/4)) membership oracle queries (querying whether a set S contains an e), where ε is a fixed constant.
In this work, we improve the query complexity of (2−η)-estimating the metric Steiner tree weight to Õ(n^(5/3)) by showing a (1/2,ε⋅|U|)-estimate for the above set cover problem using Õ(|F|^(5/3)) membership queries. To design our set cover algorithm, we estimate the size of a random greedy maximal matching for an auxiliary multigraph that the algorithm constructs implicitly, without access to its adjacency list or matrix.