论文标题
大约距离甲骨文遭受多个顶点故障
Approximate Distance Oracles Subject to Multiple Vertex Failures
论文作者
论文摘要
给定无向图$ g =（v，e）的$ n $顶点和$ m $边缘，重量为$ [1，w] $，我们构造了顶点敏感距离甲骨文（VSDO），它们是图形预处理的数据结构，并回答以下疑问：给出以下类型（近似值）$ u $和$ v $ in $ g-d $中的距离（即，删除$ d $中的顶点的图形$ g $）。 An oracle has stretch $α$ if it always holds that $δ_{G-D}(u,v)\le\tildeδ(u,v)\leα\cdotδ_{G-D}(u,v)$, where $δ_{G-D}(u,v)$ is the actual distance between $u$ and $v$ in $G-D$, and $\tildeδ(u,v)$ is the甲骨文报告的距离。 在本文中，我们为任何数字$ d $失败构建有效的VSDO。对于任何常量的$ c \ geq 1 $，我们提出了两个oracles： $ \ bullet $第一个甲骨文具有$ n^{2+1/c}（\ log n/ε）^{o（d）} \ cdot \ log w $，在$ {\ rm poly}（\ rm poly}（\ log n，d^c，d^c，d^c，log w w w w wog）中回答查询，\ log w w w w w w w log \ log \ log \ log w，ε^，ε^{ - ε^{-1 $ 1 $ 1 $ 1 $ 1+1++三. $ \ bullet $第二Oracle的大小$ n^{2+1/c} {\ rm poly}（\ log（nw），d）$，在$ {\ rm poly}中回答查询（\ rm poly}（\ log n，d^c，d^c，\ log \ log \ log \ log \ log \ log \ log w）$ time，并具有stretch $ {\ rm poly}（\ rm poly}（\ rm poly}（\ rm poly} $ n，d）$ n，d）$ n，d）。 这两个口腔都可以在其空间复杂性中进行多项式进行预处理。这些结果是对于任何恒定数量的顶点故障，通常在无向图中的任何恒定数量的顶点故障时，多形载体查询时间的第一个大约距离甲骨文。以前有$（1+ε）$ - 大约$ d $ - 边缘敏感距离甲骨文[Chechik等。 [2017]回答距离查询时，当$ d $ edges失败时，它们的大小$ o（n^2（\ log n/ε）^d \ cdot d \ log w）$和查询时间$ {\ rm poly}（\ log n，d，d，d，\ log log \ log \ log \ log \ w）$。
Given an undirected graph $G=(V,E)$ of $n$ vertices and $m$ edges with weights in $[1,W]$, we construct vertex sensitive distance oracles (VSDO), which are data structures that preprocess the graph, and answer the following kind of queries: Given a source vertex $u$, a target vertex $v$, and a batch of $d$ failed vertices $D$, output (an approximation of) the distance between $u$ and $v$ in $G-D$ (that is, the graph $G$ with vertices in $D$ removed). An oracle has stretch $α$ if it always holds that $δ_{G-D}(u,v)\le\tildeδ(u,v)\leα\cdotδ_{G-D}(u,v)$, where $δ_{G-D}(u,v)$ is the actual distance between $u$ and $v$ in $G-D$, and $\tildeδ(u,v)$ is the distance reported by the oracle. In this paper we construct efficient VSDOs for any number $d$ of failures. For any constant $c\geq 1$, we propose two oracles: $\bullet$ The first oracle has size $n^{2+1/c}(\log n/ε)^{O(d)}\cdot \log W$, answers a query in ${\rm poly}(\log n,d^c,\log\log W,ε^{-1})$ time, and has stretch $1+ε$, for any constant $ε>0$. $\bullet$ The second oracle has size $n^{2+1/c}{\rm poly}(\log (nW),d)$, answers a query in ${\rm poly}(\log n,d^c,\log\log W)$ time, and has stretch ${\rm poly}(\log n,d)$. Both of these oracles can be preprocessed in time polynomial in their space complexity. These results are the first approximate distance oracles of poly-logarithmic query time for any constant number of vertex failures in general undirected graphs. Previously there are $(1+ε)$-approximate $d$-edge sensitive distance oracles [Chechik et al. 2017] answering distance queries when $d$ edges fail, which have size $O(n^2(\log n/ε)^d\cdot d\log W)$ and query time ${\rm poly}(\log n, d, \log\log W)$.
