论文标题
确定性替换路径覆盖
Deterministic Replacement Path Covering
论文作者
论文摘要
在本文中，我们提供了一种统一而简化的方法，以使中心耐受耐受算法算法的中心结果扩散。给定V（g）\ times v（g）$中的$ g $，一个顶点$（s，t）\，以及一组边缘故障$ f \ subseteq e（g）$，a替换路径$ p（s，t，f）$是$ s $ s $ s $ s- $ t $ t $ t $ t $ f $ g \ g \ setminus f $。对于整数参数，$ l，f $，替换路径覆盖（RPC）是$ g $的子图集的集合，由$ \ textit {g} _ {g} _ {l，f} = \ {g_1，\ ldots，g_r \} $ for y。替换路径$ p（s，t，f）$最多$ l $ edges，存在一个子图$ g_i \ in \ textit {g} _ {l，f} $，其中包含$ p $的所有边缘，并且不包含$ f $的任何边缘。然后将RPC $ \ textit {g} _ {l，f} $的覆盖值定义为$ \ textit {g} _ {l，f} $中的子图数。 我们提出了$（l，f）$ -RPC的有效确定性结构，其覆盖值几乎与随机值相匹配，对于广泛的参数。与先前的parter构造相比，我们的时间和价值界限大大提高（Disc 2019）。我们还为这些覆盖物的价值提供了几乎匹配的下限。我们上述确定性结构的关键应用是Weimann and Yuster的代数构造Oracle的代数构建的范式化（FOCS 2010）。确定性算法的预处理和查询时间几乎匹配随机边界。这解决了Alon，车臣和Cohen的开放问题（ICALP 2019）。
In this article, we provide a unified and simplified approach to derandomize central results in the area of fault-tolerant graph algorithms. Given a graph $G$, a vertex pair $(s,t) \in V(G)\times V(G)$, and a set of edge faults $F \subseteq E(G)$, a replacement path $P(s,t,F)$ is an $s$-$t$ shortest path in $G \setminus F$. For integer parameters $L,f$, a replacement path covering (RPC) is a collection of subgraphs of $G$, denoted by $\textit{G}_{L,f}=\{G_1,\ldots, G_r \}$, such that for every set $F$ of at most $f$ faults (i.e., $|F|\le f$) and every replacement path $P(s,t,F)$ of at most $L$ edges, there exists a subgraph $G_i\in \textit{G}_{L,f}$ that contains all the edges of $P$ and does not contain any of the edges of $F$. The covering value of the RPC $\textit{G}_{L,f}$ is then defined to be the number of subgraphs in $\textit{G}_{L,f}$. We present efficient deterministic constructions of $(L,f)$-RPCs whose covering values almost match the randomized ones, for a wide range of parameters. Our time and value bounds improve considerably over the previous construction of Parter (DISC 2019). We also provide an almost matching lower bound for the value of these coverings. A key application of our above deterministic constructions is the derandomization of the algebraic construction of the distance sensitivity oracle by Weimann and Yuster (FOCS 2010). The preprocessing and query time of the our deterministic algorithm nearly match the randomized bounds. This resolves the open problem of Alon, Chechik and Cohen (ICALP 2019).
