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 × n distance matrix, along with a set of k terminal pairs (s 1 , t 1 ), . . . , (s k , t k ) ∈ V × 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.

Here, we give an O(log k)-approximation algorithm for the problem that runs in time O(n 3/2 ). Along the way, we provide the first sublinear-time algorithm for estimating the size of a Maximal Independent Set (MIS). Our algorithm runs in time O(n 3/2 /ε 2 ) under the adjacency matrix oracle model and obtains a purely multiplicative (1 + ε)-approximation. Previously, sublineartime algorithms for MIS were only known for bounded-degree graphs.