论文标题
敏感性甲骨口
Sensitivity Oracles for All-Pairs Mincuts
论文作者
论文摘要
令$ g =（v，e）$是$ n $顶点和$ m $ edges上的无向图。我们解决了$ g $中的全对敏捷的敏感性甲骨文的问题，如下所示。 建立一个紧凑的数据结构，该结构在接收任何边缘的任何一对顶点$ s，t \ in v $和任何边缘的故障（或插入）时，可以在故障后（或插入）后有效地报告$ s $和$ t $之间的mincut。 据我们所知，对于此问题，没有数据结构需要$ O（MN）$空间和非平凡的查询时间。我们提出以下结果。 - 我们的第一个数据结构占用$ {\ cal o}（n^2）$空间，并保证$ {\ cal o}（1）$查询时间来报告任何边缘失败（或插入）的结果$（s，t）$ - mincut的值。此外，可以在更新以$ {\ cal o}（n）$时间报告更新之后定义产生的$（s，t）$ - mincut的一组顶点。 - 我们的第二个数据结构以增加查询时间为代价优化空间。它需要$ {\ cal o}（m）$ space-这也是$ g $所占的空间。查询时间为$ {\ cal o}（\ min（m，n c_ {s，t}））$，其中$ c_ {s，t} $是$ s $和$ t $ in $ g $的$ c_ {s，t} $。与最知名的确定性算法相比，此查询时间的速度更快为$ω（\ min（m^{1/3}，\ sqrt {n}））$，以计算从scratch中计算$（s，t）$的确定性算法。 - 如果我们只想知道边缘的故障（或插入）是否会更改$（s，t）$ - mincut的值，我们可以在$ n $ vertices之间均匀地分发$ {\ cal o}（n^2）$ space数据结构。对于任何失败（或插入）边缘，我们只需要存储在其端点上的数据结构即可确定$（s，t）$ - mincut的值是否已更改为任何$ s，t \ in v $。
Let $G=(V,E)$ be an undirected unweighted graph on $n$ vertices and $m$ edges. We address the problem of sensitivity oracle for all-pairs mincuts in $G$ defined as follows. Build a compact data structure that, on receiving any pair of vertices $s,t\in V$ and failure (or insertion) of any edge as query, can efficiently report the mincut between $s$ and $t$ after the failure (or the insertion). To the best of our knowledge, there exists no data structure for this problem which takes $o(mn)$ space and a non-trivial query time. We present the following results. - Our first data structure occupies ${\cal O}(n^2)$ space and guarantees ${\cal O}(1)$ query time to report the value of resulting $(s,t)$-mincut upon failure (or insertion) of any edge. Moreover, the set of vertices defining a resulting $(s,t)$-mincut after the update can be reported in ${\cal O}(n)$ time which is worst-case optimal. - Our second data structure optimizes space at the expense of increased query time. It takes ${\cal O}(m)$ space -- which is also the space taken by $G$. The query time is ${\cal O}(\min(m,n c_{s,t}))$ where $c_{s,t}$ is the value of the mincut between $s$ and $t$ in $G$. This query time is faster by a factor of $Ω(\min(m^{1/3},\sqrt{n}))$ compared to the best known deterministic algorithm to compute a $(s,t)$-mincut from scratch. - If we are only interested in knowing if failure (or insertion) of an edge changes the value of $(s,t)$-mincut, we can distribute our ${\cal O}(n^2)$ space data structure evenly among $n$ vertices. For any failed (or inserted) edge we only require the data structures stored at its endpoints to determine if the value of $(s,t)$-mincut has changed for any $s,t \in V$.
