Sublinear Metric Steiner Tree via Improved Bounds for Set Cover

Abstract

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 $\tilde{O}(n^{13/7})$ queries and outputs a $(2-\hat{I}\cdot )$-estimate of the metric Steiner tree weight, where $\hat{I}\cdot >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 $\tilde{O}(|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-\hat{I}\cdot )$-estimating the metric Steiner tree weight to $\tilde{O}(n^{5/3})$ by showing a $(1/2,\epsilon \cdot |U|)$-estimate for the above set cover problem using $\tilde{O}(|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.