A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures

Abstract

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|\le 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=\hat{I}˜(\log n)$ faults, all previous oracles either have super-linear query time, linear-in-$f$ approximation [CLPR12], or exponentially worse $2^{\mathrm{poly}(k)}$ approximation dependency in $k$ [HLS24].

To appear in STOC 2026, 58 pages