Sublinear Metric Steiner Forest via Maximal Independent Set

In this work we consider the Metric Steiner Forest problem in the sublinear time model. Given a set \(V\) of \(n\) points in a metric space where distances are provided by means of query access to an \(n \times n\) distance matrix, along with a set of \(k\) terminal pairs (\((s_1, t_1), \ldots, (s_k, t_k), \in V \times V\), the goal is to find a minimum-weight subset of edges that connects each terminal pair. Although sublinear time algorithms have been studied for estimating the weight of a minimum spanning tree in both general and metric settings, as well as for the metric Steiner Tree problem, no sublinear time algorithm was known for the metric Steiner Forest problem.