# Near-Optimal Deterministic Vertex-Failure Connectivity Oracles

arXiv: https://arxiv.org/abs/2205.03930 · HTML: https://mlsanity.com/paper/2205.03930/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2022.

## Built on by (most cited first, 2 of 2)

- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [Connectivity Oracles for Predictable Vertex Failures](https://mlsanity.com/paper/2312.08489/) (2023)

## Abstract (arXiv)

We revisit the vertex-failure connectivity oracle problem. This is one of the most basic graph data structure problems under vertex updates, yet its complexity is still not well-understood. We essentially settle the complexity of this problem by showing a new data structure whose space, preprocessing time, update time, and query time are simultaneously optimal up to sub-polynomial factors assuming popular conjectures. Moreover, the data structure is deterministic. More precisely, for any integer dstar, the data structure preprocesses a graph G with n vertices and m edges in hatO(mdstar) time and uses tildeO(minm,ndstar) space. Then, given the vertex set D to be deleted where |D|=d≤ dstar, it takes hatO(d2) updates time. Finally, given any vertex pair (u,v), it checks if u and v are connected in Gsetminus D in O(d) time. This improves the previously best deterministic algorithm by Duan and Pettie (SODA 2017) in both space and update time by a factor of d. It also significantly speeds up the Omega(minmn,nω) preprocessing time of all known (even randomized) algorithms with update time at most tildeO(d5).