Speaker
Description
Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann and Martin Schirneck
Abstract: We study the problem of estimating the $ST$-diameter of a graph that is subject to a bounded number of edge failures. An \emph{$f$-edge fault-tolerant $ST$-diameter oracle} ($f$-FDO-$ST$) is a data structure that preprocesses a given graph $G$, two sets of vertices $S,T$, and positive integer $f$. When queried with a set $F$ of at most $f$ edges, the oracle returns an estimate $\widehat{D}$ of the $ST$-diameter $diam(G-F,S,T)$, the maximum distance between vertices in $S$ and $T$ in $G\,{-}\,F$. The oracle has stretch $\sigma \geq 1$ if $diam(G-F,S,T) \leq \widehat{D} \leq \sigma~diam(G-F,S,T)$. If $S$ and $T$ both contain all vertices, the data structure is called an \emph{$f$-edge fault-tolerant diameter oracle} ($f$-FDO).
We design new $f$-FDOs and $f$-FDO-$ST$s via reductions from both \emph{all-pairs} and \emph{single-source} \emph{$f$-edge fault-tolerant Distance Sensitivity Oracles} ($f$-DSOs), i.e., oracles that can estimate distances even when up to $f$ edges of $G$ fail. We obtain new tradeoffs between the size of the data structure, stretch guarantee, query and preprocessing times for $f$-FDOs and $f$-FDO-$ST$s by combining our reductions with the all-pairs/single-souce $f$-DSOs of Weimann and Yuster [FOCS 2010], Chechik et al.~[ESA 2010], Baswana and Khanna [STACS 2010], Chechik et al.~[SODA 2017], Brand and Saranurak [FOCS 2019], Duan and Ren [STOC 2020], Bilò et al.~[Algorithmica 2022], Singh and Gupta [ICALP 2018], and Baswana et al.~[SODA 2018].
We also provide an information-theoretic lower bound on the space requirement of approximate $f$-FDOs. We show that there exists a family graphs for which any $f$-FDO with sensitivity $f \ge 2$ and stretch less than $5/3$ requires $\Omega(n^{3/2})$ bits of space, regardless of the query time.