CS Paper Radar

Deterministic Fault-Tolerant Connectivity Oracles with Subquadratic Space

Merav Parter, Elad Tzalik

cs.DS math.CO ·submitted 2026-11-04 18:13 UTC · v1
theory

Abstract

A fault-tolerant (FT) connectivity oracle for an $n$-vertex graph $G=(V,E)$ determines whether $G- F$ is connected for any query set $F\subseteq E$. When the number of failures is unrestricted, prior constructions exhibited a sharp contrast between randomization and determinism: randomized oracles use only $\widetilde{O}(n)$ space [Duan and Pettie, SICOMP 2020], whereas no deterministic construction was known to improve upon storing $G$ explicitly, requiring $Θ(n^2)$ bits in the worst case. The promise that $F\subseteq E$ is essential for subquadratic space: allowing arbitrary queries $F\subseteq V\times V$ forces quadratic space. For queries containing at most $f$ failures, Khanna, Konrad, and Putterman [SODA 2027] recently constructed deterministic oracles using $\widetilde{O}(\sqrt{f}n)$ space that also report approximate distances with polylogarithmic stretch. Their result improves upon the classical $O(fn)$ space bound for deterministic connectivity oracles [Pătraşcu and Thorup, FOCS 2007], but offers no space savings over storing $G$ when $f=Θ(n^2)$. We present the first deterministic connectivity oracles with subquadratic space for failure sets of unrestricted size, using $\widetilde{O}(n^{7/4})$ space. We also establish the first polynomial separation between deterministic and randomized connectivity oracles, proving that every deterministic oracle requires $\widetildeΩ(n^{3/2})$ bits in the worst case. For queries containing at most $f$ failures, we obtain deterministic connectivity oracles using $\widetilde{O}(f^{2/5}n)$ space, improving the dependence on $f$ in the bound of Khanna et al., and prove a lower bound of $\widetildeΩ(f^{1/4}n)$ bits.

Closest papers

Nearest neighbours by meaning across the whole index.

Strong Connectivity Oracle for Multiple Failures via Rooted Flow-Augmentation

cs.DS ·2026-11-06 ·Aditya Anand, Thatchaphol Saranurak, Benyu Wang
published similarity 0.75
Abstract · SODA 2027

We present a significantly improved $k$-fault-tolerant strong connectivity oracle, one of the most basic data structures on a directed graph $G$ that, given any set $F$ of failed edges of size $|F|\le k$, answers whether $G \setminus F$ is strongly connected. For every constant $k$, our oracle only uses $n^{1+o(1)}$ space and $n^{o(1)}$ query time. No prior result can achieve $o(n^{2})$ space and $o(n)$ query time, \emph{even when $k=2$}. Previous oracles either require $Ω(n)$ query time [BCR18], or $Ω(n^2)$ space [vdBS19]. Our main technical contribution is a \emph{rooted} version of the highly successful flow augmentation technique, which may be of independent interest. Given a directed graph $G$, an integer $k$, and a source vertex $s$, we can sample a set of edges $A$ such that each minimal $s$-rooted cut of size at most $k$ becomes an $s$-rooted min-cut in $G + A$ with probability $2^{-poly(k)}n^{-o(1)}$.

0.57

Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size

cs.DS ·2026-09-08 ·Yaowei Long, Seth Pettie, Thatchaphol Saranurak
similarity 0.70
Abstract · 11 pages

For an undirected graph $G = (V,E)$ and a fault bound $f$, an edge-fault-tolerant connectivity labeling scheme assigns short labels to vertices and edges, so that for any vertex pair $(s,t)$ and failed edge set $F\subseteq E$ with $|F|\leq f$, the connectivity between $s$ and $t$ in $G-F$ can be answered by inspecting only the labels of $s$, $t$ and edges in $F$. In this paper, we present a labeling scheme that uses $O(\log^{2}n)$-bit labels that can be computed in deterministic polynomial time. This improves upon the previous $\tilde{O}(\sqrt{f})$ deterministic bound of [Long, Pettie, Saranurak'25], and even slightly improves the $O(\min\{f+\log n,\log^{2}n\log f\})$ randomized bound of [Dory, Parter'21] and [Long, Pettie, Saranurak'25] when $f = Ω(\log^{2}n)$. Moreover, for a general $f$, this is the first labeling scheme that produces an $\tilde{O}(1)$-size labeling which is simultaneously correct across all queries. Our approach combines the cycle-space-based labeling scheme from Dory and Parter with a recent result by [Knauer'26] on sparse cycle bases.

0.37

Vertex-Failure Distance Oracles and Labeling Schemes: Compact and Constant-Approximate

cs.DS ·2026-10-01 ·Yaowei Long
top venue similarity 0.68
Abstract · 80 pages, to appear in FOCS 2026

We present new algorithms for the vertex-failure distance oracles and labeling schemes problems in undirected weighted graphs. A vertex-failure distance oracle is a data structure that, given two vertices $x$ and $y$ and a failed vertex set $F$ of size at most $f$, returns an approximation to the distance between $x$ and $y$ in $G \setminus F$. In the labeling-scheme setting, the data structure needs to be stored distributively as labels on the vertices, and each query $(x,y,F)$ must be answered by accessing only the labels of the vertices in $F \cup \{x,y\}$. For any $f\geq 1$ and $k \ge 1$, we obtain a vertex-failure distance oracle with $O(k^{6})$ approximation, space $\tilde{O}(f^{2}n^{1+1/k})$, query time $\tilde{O}(f^{5}n^{1/k})$, and polynomial preprocessing time. In particular, this is the first time-efficient oracle for multiple vertex failures with space close to linear, as well as the first constant-approximation oracle with polynomial space when tolerating $Ω(\log n)$ vertex failures. The previous results, due to [Duan-Gu-Ren, SODA'21], gave two alternatives: for any constant $c \ge 1$ and $ε>0$, one oracle has $\mathrm{poly}(\log n,f)$ approximation, space $n^{2+1/c}\mathrm{poly}(\log n,f)$, and query time $\mathrm{poly}(\log n,f^{c})$, while the other has $(1+ε)$ approximation, space $n^{2+1/c}(\log n/ε)^{O(f)}$, and query time $\mathrm{poly}(\log n,f^{c},1/ε)$. We also obtain a vertex-failure distance labeling scheme with $O(k^{6})$ approximation and label size $f^{3}n^{1/k}\log^{O(k)} n$. This is the first nontrivial distance labeling scheme for vertex failures. Our techniques build on recent tools related to length-constrained vertex expanders and also introduce a new expander-based shortcut sparsification. The latter also leads to a deterministic vertex-failure connectivity labeling scheme of size $\tilde{O}(f^{2})$.

0.32

Connectivity in a New Bounded-Space Dynamic Model

cs.DS ·2026-11-05 ·Bardiya Aryanfard, Monika Henzinger, John Kuszmaul, Jakob Nogler, Virginia Vassilevska Williams
theory similarity 0.66
Abstract · Submitted to STOC; shortened abstract to fit arxiv requirements

We introduce a new model for dynamic algorithms in which the algorithm has read-only oracle access to a dynamically changing input and random access to its own bounded workspace. It is a dynamic analogue of the time-space tradeoffs for static inputs studied in complexity theory, where only writable memory counts as space. We study dynamic undirected $s$-$t$ connectivity: after every edge update to an $n$-vertex graph, an algorithm with $S$ words of workspace must report whether $s$ and $t$ are connected. The graph is accessed via adjacency list queries (degree, $j$-th neighbor) or adjacency matrix queries. Our algorithms are randomized; our lower bounds hold for randomized algorithms with $cn$ bits of workspace, $c>0$ a small constant ($cn/\log n$ for the worst-case matrix bound). We prove: (1) With adjacency lists, worst-case time $\tildeΘ(n^2/S^2)$ per insertion is necessary and sufficient for incremental algorithms. (2) With an adjacency matrix, worst-case time $\tildeΩ(n^2/S)$ per insertion is necessary for incremental algorithms, and sufficient for $S\ge\sqrt{n}$. (3) With amortization, incremental algorithms achieve $\tilde O(n/S)$ time per insertion with adjacency lists and $\tilde O(n^2/S)$ with an adjacency matrix, while $\tildeΩ(\sqrt{n/S})$ and $\tildeΩ(n\sqrt{n/S})$, respectively, are necessary. (4) Fully dynamic algorithms need amortized time $\tildeΩ(n/S)$ per update with adjacency lists and $\tildeΩ(n^2/S)$ with an adjacency matrix, even on forests, where both bounds are tight (lists: under bounded degree). Conventional dynamic connectivity admits polylogarithmic update time with $Ω(n)$ words of space. In contrast, our lower bounds show that polynomial update time is necessary whenever $S\le n^{1-\varepsilon}$, even for a single pair of vertices and even for incremental algorithms with amortized guarantees.

0.26

A Tight Space Lower Bound for Pivot-Based Distance Oracles

cs.DS ·2026-10-21 ·Avi Kadria, Liam Roditty
theory similarity 0.65
Abstract

An approximate distance oracle (ADO) is a compact data structure that answers distance queries within a multiplicative \emph{stretch} $k$. The classical oracle of Thorup and Zwick~[STOC'01, JACM'05] has stretch $k=2\ell-1$ and uses $O(\ell n^{1+1/\ell})$ space, for every integer $\ell\ge1$. This trade-off is optimal for dense graphs under the Erdős girth conjecture. However, for sparse graphs ($m=O(n)$), their lower bound yields nothing beyond $Ω(m)$ space. The main result of this paper is a nearly tight lower bound for pivot-based $1$-hop ADOs in sparse graphs. A pivot-based $1$-hop ADO gives every vertex $\tilde{O}(1)$ pivots and returns as an estimate the length of a walk of the form $u\to p_u \to p_v \to v$, where $p_u$ is a pivot of $u$, $p_v$ is a pivot of $v$, and $p_u\to p_v$ is a stored distance. We observe that all the state-of-the-art ADOs with $\tilde{O}(1)$ query time are in fact pivot-based $1$-hop ADOs. We prove that every \emph{pivot-based} $1$-hop ADO with \emph{real} stretch $k$ requires $\widetildeΩ(m^{1+2/(k+1)})$ space, under the Erdős girth conjecture for graphs with constant degree. This matches the best known ADOs with $\tilde{O}(1)$ query time, at every known stretch, up to polylogarithmic factors. We also extend our lower bound to pivot-based ADOs with any constant number $β$ of hops, showing that they require $\widetildeΩ(m^{1+2/(β(k+1))})$ space. In addition, we obtain a tight lower bound for two-hop hopsets and improved lower bounds for general $β$-hop hopsets.

0.24

A Better Lower Bound for Sublinear Metric Steiner Tree

cs.DS ·2026-10-30 ·Sepideh Mahabadi, Jakub Tarnawski, Ali Vakilian
theory similarity 0.63
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

Minimum Sum-of-Radii Clustering with Strong and Weak Oracles

cs.DS ·2026-11-16 ·Zachary Friggstad, Mahya Jamshidian, Ali Vakilian
theory similarity 0.63
Abstract · 42 pages

In the minimum sum of radii (MSR) problem, the input is a set of $n$ points in a metric space and a parameter $k$, and the goal is to cover the points by at most $k$ balls, each centered at an input point, while minimizing the sum of their radii. We study MSR in the weak-strong oracle model of Bateni, Dharangutte, Jayaram, and Wang (COLT'24), where the metric is unknown and is accessed through two oracles. The answers of the weak oracle are given to us for free: for every pair of points, we receive a distance value that, with probability $δ$, is arbitrarily corrupted. Exact distances are available only through costly strong queries, where a strong query on a point reveals its exact distances to all previously strongly queried points, and the goal is to minimize the number of strong queries. For every constant $δ< 1/2$, we give the first polynomial-time algorithm that makes $O(k \log n \log\log n)$ strong point queries and, with high probability, returns an $O(1)$-approximation for MSR; the previously best algorithm required running time and a number of strong queries exponential in $k$. This is within an $O(\log\log n)$ factor of a lower bound that we prove: any constant-factor approximation that succeeds with high probability on every instance must make $Ω(k \log n)$ strong queries in expectation on some instance. The same $Ω(k \log n)$ lower bound holds for $k$-center, where it matches the known upper bound up to an $O(\log\log n)$ factor. An optimal MSR cluster can be small both in size and in radius, so a uniform sample of strongly queried points may miss it entirely. Instead, our algorithm uses a packing LP over the balls certified so far to decide which points to query next. The analysis holds against an adversary who knows which pairs are corrupted.

0.10

A Simple Subquadratic Cut Query Protocol for Directed Reachability

cs.DS ·2026-11-04 ·Henry Fleischmann, Sagnik Mukhopadhyay, Swagato Sanyal
similarity 0.62
Abstract · 17 + 22 pages

We study $s$--$t$ reachability in an unweighted directed graph on $n$ vertices, accessed through a directed cut oracle: given $S\subseteq V$, the oracle returns the number of edges directed from $S$ to $V\setminus S$. Directed cut functions are submodular, and reachability asks whether the minimum $s$--$t$ cut has positive value. This connects the problem to the query complexity of submodular function minimisation. Whether or not reachability can be solved in truly subquadratic query complexity has been an outstanding open question for a decade. We give a simple algorithmic blueprint with two randomised implementations. The first uses $\widetilde O(n^{9/5})$ outgoing-cut queries; the second improves this bound to $\widetilde O(n^{5/3})$. The common idea is to construct an alternative orientation with the same underlying undirected graph and vertex-wise degree imbalances, thereby preserving reachability. We first approximate the target imbalances using an averaging and rounding procedure, then correct the remaining error with a flow. An earlier manuscript, made available in August 2026 in an online AI repository, reports an $\widetilde O(n^{3/2})$ query bound. Our contribution is a simple and comprehensible alternative approach that already achieves a polynomial saving over quadratic query complexity.

0.54