The Taub Faculty of Computer Science Events and Talks

Given an undirected weighted graph, a distance oracle is a data structure that answers distance queries in the graph within a short time. A path-reporting distance oracle (PRDO) is a distance oracle that is also required to return a shortest path between the queried vertices. A particular interest is in oracles that have a linear storage size in the number of vertices of the input graph, and also have small query time and a good approximation factor (called the stretch). Throughout the years, there was a major progress in the results for non-path-reporting distance oracles, and an almost optimal trade-off between size, query time and stretch was achieved (“optimal” up to the widely believed girth conjecture by Erdos). However, for PRDOs, such near-optimal results were never accomplished. In our work, we construct PRDOs with almost the same near-optimal trade-off as of non-path-reporting distance oracles. On our way to these results, we introduce notions of interactive graph structures, that capture the functionality of both PRDOs and some other combinatorial structures, such as spanners, emulators and distance preservers. A joint work of Michael Elkin and Idan Shabat.