DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.90

Approximate Single Source Dual Fault Tolerant Distance Oracle

Authors: Koustav Das and Manoj Gupta

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

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 Õ(n√n) space and has Õ(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 Õ(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.

Cite as

Koustav Das and Manoj Gupta. Approximate Single Source Dual Fault Tolerant Distance Oracle. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 90:1-90:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ESA.2026.90,
  author =	{Das, Koustav and Gupta, Manoj},
  title =	{{Approximate Single Source Dual Fault Tolerant Distance Oracle}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{90:1--90:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.90},
  URN =		{urn:nbn:de:0030-drops-272263},
  doi =		{10.4230/LIPIcs.ESA.2026.90},
  annote =	{Keywords: Fault-tolerant distance oracle, Shortest paths, Graph algorithms, Dual failures, Approximate distance oracle}
}

Search Results

Documents authored by Das, Koustav

Approximate Single Source Dual Fault Tolerant Distance Oracle

Abstract

Cite as

Thanks for your feedback!

Could not send message