论文标题
在失败下的新型极端界限，可达到可及性和强烈连接性保存器
New Extremal bounds for Reachability and Strong-Connectivity Preservers under failures
论文作者
论文摘要
在本文中，我们考虑了计算$ n $顶点和$ m $边缘的任何输入的$ g =（v，e）$计算稀疏子图的问题，该问题可保留可达性和/或强连接性结构。 我们显示$ O（N+\ min \ {| {\ cal P} | \ sqrt {n}，n \ sqrt {| {| {\ cal p} |} |} \}）$绑定在一个子图上，该子图是一个$ 1 $ - 可耐耐受性的pertex-pair time $ perte $ $ $} $} $ {即，它可以在单个边缘（或顶点）故障下保留$ {\ cal p} $中任何一对顶点之间的可达性。我们的结果是比以前的最佳$ o（n | {\ cal p} |）$有了显着改善，作为单源可及性保存器结构的必然性获得。我们通过利用任何对的单个耐受耐受性可及性保存器的特殊结构来证明我们的上限，然后考虑不同对的结构之间的相互作用。 在下边界，我们表明，顶点式的2耐耐受性可及性保存器$ {\ cal p} \ subseteq v \ subseteq v \ times v $ size $ω（n^ε）$，即使对于任何任意的小$ $ε$，至少都要求至少$ω（n^{1+ε/8}）$ edges。对于任何多项式大小的顶点对组，这驳斥了线性大小的双断层耐耐剂的存在。 我们还介绍了最多$ \ tilde {o}（k 2^k n^{2-1/k}）$的第一个子界限，用于在$ k $ failures下有针对性图的强连接性保存器。据我们所知，以前没有针对此问题的非平凡限制，以$ k $的一般。我们通过采用Alon，Yuster和Zwick [JACM'95]的颜色编码技术来获得结果。
In this paper, we consider the question of computing sparse subgraphs for any input directed graph $G=(V,E)$ on $n$ vertices and $m$ edges, that preserves reachability and/or strong connectivity structures. We show $O(n+\min\{|{\cal P}|\sqrt{n},n\sqrt{|{\cal P}|}\})$ bound on a subgraph that is an $1$-fault-tolerant reachability preserver for a given vertex-pair set ${\cal P}\subseteq V\times V$, i.e., it preserves reachability between any pair of vertices in ${\cal P}$ under single edge (or vertex) failure. Our result is a significant improvement over the previous best $O(n |{\cal P}|)$ bound obtained as a corollary of single-source reachability preserver construction. We prove our upper bound by exploiting the special structure of single fault-tolerant reachability preserver for any pair, and then considering the interaction among such structures for different pairs. In the lower bound side, we show that a 2-fault-tolerant reachability preserver for a vertex-pair set ${\cal P}\subseteq V\times V$ of size $Ω(n^ε)$, for even any arbitrarily small $ε$, requires at least $Ω(n^{1+ε/8})$ edges. This refutes the existence of linear-sized dual fault-tolerant preservers for reachability for any polynomial sized vertex-pair set. We also present the first sub-quadratic bound of at most $\tilde{O}(k 2^k n^{2-1/k})$ size, for strong-connectivity preservers of directed graphs under $k$ failures. To the best of our knowledge no non-trivial bound for this problem was known before, for a general $k$. We get our result by adopting the color-coding technique of Alon, Yuster, and Zwick [JACM'95].
