A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
This provides a foundational improvement for graph algorithms, enabling efficient distance queries under edge failures with broad applications in network reliability and distributed systems.
The paper tackles the problem of designing a fault-tolerant distance labeling scheme for undirected weighted graphs that can handle any number of edge failures, achieving a constant approximation ratio of O(k^4) with label size Õ(f^4 n^{1/k}), which resolves an open problem from prior work where approximations were linear in f.
A fault-tolerant distance labeling scheme assigns a label to each vertex and edge of an undirected weighted graph $G$ with $n$ vertices so that, for any edge set $F$ of size $|F| \leq f$, one can approximate the distance between $p$ and $q$ in $G \setminus F$ by reading only the labels of $F \cup \{p,q\}$. For any $k$, we present a deterministic polynomial-time scheme with $O(k^{4})$ approximation and $\tilde{O}(f^{4}n^{1/k})$ label size. This is the first scheme to achieve a constant approximation while handling any number of edge faults $f$, resolving the open problem posed by Dory and Parter [DP21]. All previous schemes provided only a linear-in-$f$ approximation [DP21, LPS25]. Our labeling scheme directly improves the state of the art in the simpler setting of distance sensitivity oracles. Even for just $f = Î(\log n)$ faults, all previous oracles either have super-linear query time, linear-in-$f$ approximation [CLPR12], or exponentially worse $2^{{\rm poly}(k)}$ approximation dependency in $k$ [HLS24].