arXiv preprint ·
Improved Sublinear Algorithms for Maximal Independent Set and Metric Steiner Forest
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In this work we consider the Maximal Independent Set (MIS) problem and the metric Steiner Forest problem in the sublinear time setting, under the adjacency/distance matrix query model. First, we give an algorithm that estimates the size of an MIS up to a multiplicative factor of $(1+\eps)$ using $\tO(n^{4/3}/\eps^2)$ queries. This improves the best previous algorithm by Mahabadi, Roghani, Tarnawski, and Vakilian (SODA 2026), which had a query complexity of $\tO(n^{3/2}/\eps^2)$. Via a reduction from that work, this would automatically imply the same improvement for the problem of estimating the metric Steiner Forest cost up to an $O(\log n)$ factor. However, as our second contribution, we consider the Steiner Forest problem directly and provide an algorithm with $\tO(n)$ query complexity that is very simple and does not proceed via MIS.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Fast mixing of the SYK model at high temperatures
Explicit Asymptotic Bounds for Sequential Calibration Beyond $T^{2/3}$
Near-Exact Computation of Independent Chip Model Placement Probabilities for Thousands of Players
How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics
When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.