2026-08-25T17:34:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27226 2026-08-25T13:18:18Z ddc:004 open_access

Approximate Single Source Dual Fault Tolerant Distance Oracle Das, Koustav Gupta, Manoj Fault-tolerant distance oracle Shortest paths Graph algorithms Dual failures Approximate distance oracle We are given an undirected weighted graph G with n vertices and m edges, edge weights in [1, W], and a designated source vertex s. We design a single source dual fault tolerant distance oracle for G. Given a destination vertex t and a set F of at most two faulty edges, the oracle returns a (1 + O(ε))-approximation of the weight of the shortest path from the source s to t avoiding F. Our oracle uses Õ(n√n) space and has Õ(1) query time. Prior to our result, single source single fault tolerant oracles were known to return a (1+ε) approximation of the weight of the shortest path using Õ(n) space and O(1) query time. However, extending these approaches to multiple faults remained an open problem. Indeed, all (1+ε)-approximate distance oracles that handle multiple faults require Ω(n²) space. We break this bound by presenting the first dual fault tolerant distance oracle with o(n²) space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Koustav Das and Manoj Gupta 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.90 urn:nbn:de:0030-drops-272263 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.90 eng https://creativecommons.org/licenses/by/4.0/legalcode