Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs

Abstract

We present a labeling scheme that assigns labels of size $\tilde{O}(1)$ to the vertices of a directed weighted planar graph $G$, such that for any fixed $\epsilon >0$ from the labels of any three vertices $s$, $t$ and $f$ one can determine in $\tilde{O}(1)$ time a $(1+\epsilon )$-approximation of the $s$-to-$t$ distance in the graph $G\setminus \{f\}$. For approximate distance queries, prior to our work, no efficient solution existed, not even in the centralized oracle setting. Even for the easier case of reachability, $\tilde{O}(1)$ queries were known only with a centralized oracle of size $\tilde{O}(n)$ [SODA 21].

To appear in STOC 2025