Approximate Single Source Dual Fault Tolerant Distance Oracle

Title of the Talk: Approximate Single Source Dual Fault Tolerant Distance Oracle
Host Faculty: Prof.Subrahmanyam Kalyanasundaram
Speaker: Koustav Das
Date: 11 August 2026
Time: 04:00 pm
Meeting Link: https://meet.google.com/qpn-rdkk-mvp

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 Õ(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.

This work is a collaboration with Prof. Manoj Gupta and has been accepted at ESA 2026.

Bio
Koustav Das is a PhD student at IIT Gandhinagar, advised by Prof. Manoj Gupta. His research focuses on fault-tolerant distance oracles and approximate shortest path structures in graphs. He completed his M.Sc. at Ramakrishna Mission Vivekananda Educational and Research Institute and his B.Sc. at Ramakrishna Mission Vidyamandira.