论文标题
近乎最佳的确定性顶点 - 网络连通性甲骨沟
Near-Optimal Deterministic Vertex-Failure Connectivity Oracles
论文作者
论文摘要
我们重新访问顶点 - 易位连接性甲骨文问题。这是顶点更新下最基本的图形数据结构问题之一，但其复杂性仍然没有得到充分理解。从本质上讲，我们通过显示一种新的数据结构来解决此问题的复杂性，其空间，预处理时间，更新时间和查询时间是同时最佳的，即假设流行的猜想，则可以最佳地达到亚物种分解因素。此外，数据结构是确定性的。 更准确地说，对于任何整数$ d _ {\ star} $，数据结构预处理$ g $带有$ n $顶点，$ n $顶点和$ \ hat {o}（md _ {\ star} $ in $ \ hat {o {\ star}）$ time and time and time and and $ \ tilde {o} $}（然后，给定为删除的顶点集$ d $，其中$ | d | = d \ le d _ {\ star} $，它采用$ \ hat {o}（d^{2}）$更新时间。最后，考虑到任何顶点对$（u，v）$，它检查$ u $和$ v $是否在$ o（d）$ time中连接为$ g \ setminus d $。这将Duan和Pettie（Soda 2017）在太空和更新时间上的最佳确定性算法提高了$ D $。它还可以显着加快$ω（\ min \ {mn，n^ω\}）$的预处理时间的所有已知（甚至随机）算法的预处理时间，最多$ \ tilde {o}（o}（d^{5}））$。
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}(md_{\star})$ time and uses $\tilde{O}(\min\{m,nd_{\star}\})$ space. Then, given the vertex set $D$ to be deleted where $|D|=d\le d_{\star}$, it takes $\hat{O}(d^{2})$ updates time. Finally, given any vertex pair $(u,v)$, it checks if $u$ and $v$ are connected in $G\setminus 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 $Ω(\min\{mn,n^ω\})$ preprocessing time of all known (even randomized) algorithms with update time at most $\tilde{O}(d^{5})$.
