CS Paper Radar

Faster Sublinear Maximal Independent Set Size

Peter Kiss, Arash Kooroshnezhad

cs.DS ·submitted 2026-10-02 16:56 UTC · v2

Abstract

We give a sublinear-time algorithm for estimating the size of a maximal independent set in a graph using adjacency-query access with expected running time $\tilde{O}(n^{1+1/3})$, improving over the previous $\tilde{O}(n^{1+1/2})$ bound of Mahadabi et al. [MRTV26]. As a consequence of a reduction of [MRTV26], this also improves the running time for sublinear metric Steiner forest. We further show that a bi-criteria estimate of the $k$-center objective in general metrics can be obtained via a reduction to maximal independent set size estimation.

Closest papers

Nearest neighbours by meaning across the whole index.

Improved Sublinear Algorithms for Maximal Independent Set and Metric Steiner Forest

cs.DS ·2026-10-05 ·Sepideh Mahabadi, Jakub Tarnawski
similarity 0.81
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.

0.43

An $n^{0.3+\varepsilon}$-Approximation for Steiner $k$-Forest

cs.DS ·2026-10-07 ·Eden Chlamtáč
similarity 0.70
Abstract

We give an $n^{0.3+\varepsilon}$-approximation algorithm for the Steiner $k$-Forest problem, for any constant $\varepsilon>0$. As a function of $n$, this improves over the $O(\min\{\sqrt{n},\sqrt{k}\})$-approximation of Gupta et al. [ESA'07, TALG'10] which has stood for nearly two decades for the general case, as well as the later $n^{0.448}$-approximation of Dinitz et. al [APPROX-RANDOM'14, TALG'17] for the uniform weight case. On the other hand, we show that, due to lower bounds on the Densest $k$-Subgraph problem, the $O(\sqrt k)$-approximation for Steiner $k$-Forest likely cannot be improved. Specifically, we show that for any sufficiently small $\varepsilon>0$, an $O(k^{1/2-\varepsilon})$-approximation for Steiner $k$-Forest would surpass known degree-$n^{Ω(\varepsilon^2)}$ Sum-of-Squares integrality gaps for Densest k-Subgraph and refute the corresponding dense-versus-random conjecture.

0.20

Tight Bounds for Sublinear Metric Steiner Tree

cs.DS ·2026-11-09 ·Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian
theory similarity 0.68
Abstract

In the metric Steiner tree problem we are given an $n$-point metric space $(V,w)$ and a set $T\subseteq V$ of terminals, and we seek the smallest weight $\mathrm{OPT}$ of a tree that spans $T$ and may use points of $V\setminus T$. We study sublinear algorithms in the distance-oracle model, where the algorithm knows $V$ and $T$ upfront and can query the distance function $w$. The objective is to estimate $\mathrm{OPT}$ while querying significantly fewer than $n^2$ distances. The minimum spanning tree on $T$ estimates $\mathrm{OPT}$ within a factor $2$, and its weight can be approximated with $\widetilde{O}(n)$ queries. The natural question that has been studied is therefore the query complexity of estimating $\mathrm{OPT}$ within a factor strictly below $2$. Chen, Khanna, and Tan [SODA 2023] gave such an algorithm using $\widetilde{O}(n^{13/7})$ queries, and a lower bound of $\widetildeΩ(n^{6/5})$. Later Mahabadi, Roghani, Tarnawski, and Vakilian [ITCS 2025] improved the algorithm to $\widetilde{O}(n^{5/3})$, and Mahabadi, Tarnawski, and Vakilian [ITCS 2027] improved the lower bound to $\widetildeΩ(n^{7/5})$. In this work we settle the above question. We give an algorithm that estimates $\mathrm{OPT}$ within a factor $2-η_0$, for an absolute constant $η_0>0$, with query (and time) complexity $\widetilde{O}(n^{3/2})$. We also show that the exponent $3/2$ is tight.

0.12

A Better Lower Bound for Sublinear Metric Steiner Tree

cs.DS ·2026-10-30 ·Sepideh Mahabadi, Jakub Tarnawski, Ali Vakilian
theory similarity 0.64
Abstract

In the metric Steiner tree problem, we are given an $n$-point metric space $(V,w)$ and a set of terminals $T\subseteq V$, and we are interested in the smallest total weight $\mathsf{st}(V,T,w)$ of a tree that contains every terminal and may also use points of $V\setminus T$. We work in the distance-oracle model: the algorithm knows $V$ and $T$ in advance and learns $w$ only by querying a single entry $w(u,v)$ at a time. The goal is to estimate $\mathsf{st}(V,T,w)$ with the minimum number of queries. A factor of $2$ is achievable with nearly linear number of queries, so the interesting question is the query complexity of algorithms with an approximation ratio strictly below $2$. We prove that for every fixed $η\in(0,1)$, every randomized $(2-η)$-approximation algorithm must make more than $\widetildeΩ(n^{7/5})$ queries, improving upon the previously known bound of $\widetildeΩ(n^{6/5})$. Given that the best known upper bound shows that $\widetilde O(n^{5/3})$ queries suffice, the exponent of this problem now lies between $7/5$ and $5/3$, up to logarithmic factors.

0.20

On (Directed) Width-Parameters of Geometric Spanners

cs.CG ·2026-09-18 ·Kevin Buchin, Carolin Rehs, Torben Scheele
published similarity 0.62
Abstract · Accepted at ISAAC 2026

To speed up algorithms on geometric graphs, it is common to approximate the complete Euclidean graph while maintaining certain geometric properties. A (directed) $t$-spanner $G$ for a point set $P$ in the Euclidean space is a (directed) graph such that for every pair of points, the shortest path in $G$ is at most a factor $t$ longer than the Euclidean distance between those points. In this paper, we investigate $t$-spanners that are bounded by certain graph parameters. Let $κ$ be a graph parameter. We show that for path-width, branch-width and cut-width there is an $\mathcal{O}(n/k^{d/(d-1)})$-spanner $G$ on $P$ with $κ(G)=k$ and that this is asymptotically worst-case optimal. In $\mathbb{R}^2$ we show the same bounds for planar graphs of clique-width or rank-width $k$. In contrast, for tree-depth, we show that there are sets of points for which the dilation cannot be bounded. Therefore, we investigate computing a spanner with tree-depth $k$ and minimum dilation. We show that already for tree-depth $3$ this problem is NP-hard to approximate within any factor strictly less than $\sqrt{2}$, and present an XP-algorithm to compute for a given tree-depth $k$ a graph with dilation at most $2t^*$, where $t^*$ is the minimum dilation. We further extend these results to obtain directed $\mathcal{O}(n/k^{d/(d-1)})$-spanners $G$ with $κ(G)=k$ for $κ$ being directed tree-width, directed path-width or DAG-width and show that also in the directed case, this is asymptotically worst-case optimal.

0.29

Bicriteria Approximate Navigable Graphs in General Metrics

cs.DS ·2026-10-25 ·Hongyi Chen, Tianyi Zhang
top venue similarity 0.60
Abstract · To appear in SODA 2027

We study approximation algorithms for constructing sparse navigable graphs in general metrics. Given an $n$-point metric $(P,d)$ and a parameter $α\ge 1$, an $α$-navigable graph is a directed graph $G=(P,E)$ such that for every ordered pair of distinct points $s,t\in P$, the vertex $s$ has an outgoing edge $(s,p)$ with $d(p,t)<d(s,t)/α$. The objective is to minimize the number of edges. Approximation algorithms for this problem were recently studied by Khanna, Padaki, and Waingarten (SODA 2026), and independently by Conway et al. (SODA 2026). These works show that the single-criterion problem faces a Set Cover barrier: an $O(\log n)$-approximation is achievable, whereas obtaining an $o(\log n)$-approximation is NP-hard. To obtain faster algorithms, Khanna, Padaki, and Waingarten introduced bicriteria approximation, in which the output graph is required to be $α$-navigable, while its size is compared against that of an optimal $β$-navigable graph for some relaxed parameter $β\ge α$. They gave a fast matrix-multiplication-based algorithm that computes an $(α,2(1+\varepsilon)α)$-bicriteria $O(\log n)$-approximation in time $\widetilde O(n^ω\log Δ/\varepsilon)$, where $Δ$ denotes the aspect ratio and $ω$ is the matrix multiplication exponent. Our main result is a simpler near-quadratic-time algorithm with stronger bicriteria guarantees. For every constant $α\ge 1$, we compute in time $\widetilde O(n^2\logΔ)$ an $α$-navigable graph that is simultaneously an $(α,2α+O(1))$-bicriteria $O(1)$-approximation and an $(α,α+O(1))$-bicriteria $O(\log n)$-approximation. We complement the algorithm with a hardness result showing that for every constant $η\in(0,1)$, no polynomial-time algorithm can compute an $(α,2α-η)$-bicriteria $o(\log n)$-approximation unless $P=NP$.

0.34

On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search

cs.DS cs.LG ·2026-10-28 ·Majid Daliri, Mohammadreza Daneshvaramoli, Purna Dutta, Edo Liberty, Cameron Musco +2 more
theory similarity 0.60
Abstract

Graph-based nearest neighbor search algorithms like HNSW, DiskANN, NSG, and others have surged in popularity in recent years due to their excellent empirical performance in comparison to space-partitioning methods like IVF data structures and Locality Sensitive Hashing (LSH). However, in contrast to LSH and related methods, obtaining strong worst-case theoretical guarantees for graph-based search has proven challenging. In this paper, we prove a strong lower bound that helps explain the lack of progress towards such guarantees. We show that no standard graph-based method (any that runs a variant of greedy search on a flat or hierarchical graph) can achieve sublinear query time for approximate nearest neighbor search in Euclidean space, even for an arbitrarily large approximation factor. On the other hand, we prove that sublinear query time is possible if we allow for Steiner points in the search graph. We obtain bounds comparable to LSH, showing e.g., that graph-based search with Steiner points can solve $c$-approximate nearest neighbor search in Euclidean space with query time $\tilde{O}(n^{1/(c-1)})$. We complement this result with initial experiments exploring how Steiner points can be incorporated into practical graph-based methods.

0.21

Approximation and Inapproximability of Non-Preemptive Dial-a-Ride

cs.DS ·2026-10-21 ·Jingyang Zhao, Mingyu Xiao
similarity 0.59
Abstract

The non-preemptive dial-a-ride problem (DaRP) asks for a minimum-cost route of a capacitated vehicle that serves a collection of pickup-and-delivery requests, without allowing objects to be transferred or temporarily unloaded. We study this problem and the closely related minimum-ratio Steiner $k$-Forest (S$k$F) in general symmetric metrics on $n$ locations. We develop a randomized polynomial-time algorithm with expected approximation ratio $\mathcal{O}(n^{1/4}\log^{11}n)$ for the minimum-ratio S$k$F. Our algorithm combines a deterministic approximation on hierarchically well-separated trees with randomized metric embeddings. Using this algorithm, we obtain expected $\mathcal{O}(n^{1/4}\log^{12}n)$-approximations for both the non-preemptive DaRP and the S$k$F. These guarantees improve on the previous $n^{0.3+\varepsilon}$-approximation ratios for the S$k$F and the non-preemptive DaRP, where $\varepsilon>0$ is any fixed constant. Complementing these algorithmic results, we establish the first superconstant inapproximability bounds for the non-preemptive DaRP. Under the Exponential Time Hypothesis (ETH), no deterministic polynomial-time algorithm achieves an $x^{1/(\log\log x)^c}$-approximation for some constant $c>0$, where $x$ denotes either the number of locations $n$ or the vehicle capacity $k$. Under the quantitative Gap-ETH, we rule out every deterministic polynomial-time $x^{o(1)}$-approximation. These bounds hold even on unit-edge stars with $n=(2+o(1))k$.

0.21