Deterministic graph connectivity oracles use less than quadratic space
Deterministic Fault-Tolerant Connectivity Oracles with Subquadratic Space
Data Structures and Algorithms
Summary
Determining if a network remains connected after some connections fail is important for many applications. The authors provide the first way to do this using less than quadratic memory, without relying on randomness, even when many failures occur. They also prove that deterministic methods must use at least a certain amount of space, distinguishing them from randomized ones. This improves upon past methods that either used too much space or only worked well when few failures happened.
What this means in practice
- •For network engineers: Design monitoring tools that quickly check if a communication network remains connected after multiple link failures using less memory.
- •For database administrators: Optimize query systems that verify connectivity in large, failure-prone data graphs more efficiently with deterministic guarantees.
A theory result. No direct application yet.
Authors
Merav Parter, Elad Tzalik
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.