Sublinear Metric Steiner Forest via Maximal Independent Set
Preprint
Abstract
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), \dots, (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. Here, we give an $O(\log k)$-approximation algorithm for the problem that runs in time $\widetilde{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 $\widetilde{O}(n^{3/2}/\varepsilon^2)$ under the adjacency matrix oracle model and obtains a purely multiplicative $(1+\varepsilon)$-approximation. Previously, sublinear-time algorithms for MIS were only known for bounded-degree graphs.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Local Computation Algorithms for Maximum Matching: New Lower Bounds2023
- Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time2023
- Almost 3-Approximate Correlation Clustering in Constant Rounds2022
- Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time2019
- Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time2019
- Fully Dynamic Maximal Independent Set with Sublinear in n Update Time2019
- New techniques and tighter bounds for local computation algorithmsJournal of Computer and System Sciences, 2016
- Local Computation Algorithms for Graphs of Non-constant DegreesAlgorithmica, 2016
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear TimeSIAM Journal on Computing, 2009
- The Steiner tree problem on graphs: Inapproximability resultsTheoretical Computer Science, 2008