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

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| ≤ f, one can approximate the distance between p and q in G ∖ F by reading only the labels of F ∪ p,q. For any k, we present a deterministic polynomial-time scheme with O(k4) approximation and Õ(f4n1/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 [Dory and Parter, PODC 2021]. All previous schemes provided only a linear-in-f approximation [Dory and Parter, PODC 2021; Long, Pettie, Saranurak, SODA 2025]. Our labeling scheme directly improves the state of the art in the simpler setting of distance sensitivity oracles. Even for just f = Θ(logn) faults, all previous oracles either have super-linear query time, linear-in-f approximation [Chechik, Langberg, Peleg, Roditty, Algorithmica 2012], or exponentially worse 2poly(k) approximation dependency in k [Haeupler, Long, Saranurak, FOCS 2024].