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\times n\) matrix \(w\), and a set of terminals \(T\subseteq 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-\eta )\)-estimate of the metric Steiner tree weight, where \(\eta >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|-\text{SC}(U,F)\). Here \(U\) is the set of elements, \(F\) is the collection of sets, and \(\text{SC}(U,F)\) denotes the optimal set cover size of \((U,F)\). In particular, their algorithm returns a \((1/4,\epsilon \cdot |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 \(\epsilon\) is a fixed constant. In this work, we improve the query complexity of \((2-\eta )\)-estimating the metric Steiner tree weight to \(Õ_{}({n^(}_{5/3)})\) by showing a \((1/2,\epsilon \cdot |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.