Almost Tight Oracles for Fastest-Path Queries on Temporal Trees

We investigate the trade-offs between size and query time that are attainable by fastest-path oracles for temporal trees, i.e., data structures capable of reporting the duration of a fastest point-to-point temporal path, possibly constrained to be within a given time window. For any parameter t≥1 of choice, we provide an oracle of size O(M+M2t2) answering queries in time O(tlog(1+L)), where L is the maximum number of time-labels of a single edge, and M is the overall number of (not necessarily distinct) time-labels. We also prove a conditional lower bound that relies on the difficulty of the Set Disjointness problem, showing that the trade-offs obtained by our oracles are tight, up to polylogarithmic factors. We also investigate the case of general temporal graphs and we provide some evidences that the problem becomes much more challenging even for the special case of temporal reachability queries with no time constraints.