Near-Optimal Deterministic Vertex-Failure Connectivity Oracles

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 $d_{\star}$, the data structure preprocesses a graph G with n vertices and m edges in $\hat{O}\left(m d_{\star}\right)$ time and uses $\tilde{O}\left(\min \left\{m, n d_{\star}\right\}\right)$ space. Then, given the vertex set D to be deleted where $|D|=d \leq d_{\star}$, it takes $\hat{O}\left(d^{2}\right)$ updates time. Finally, given any vertex pair $(u, v)$, it checks if u and v are connected in $G \backslash D$ in $O(d)$ time. This improves the previously best deterministic algorithm by Duan and Pettie [SICOMP 2020] in both space and update time by a factor of d. It also significantly speeds up the $\Omega\left(\min \left\{m n, n^{\omega}\right\}\right)$ preprocessing time of all known (even randomized) algorithms with update time at most $\tilde{O}\left(d^{5}\right)$.