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 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).