GPU Algorithms for Fastest Path Problem in Temporal Graphs

This paper introduces the first gpu-based parallel algorithms to solve the fastest path duration (fpd) problem in temporal graphs. Fastest path duration in temporal graphs is a well studied problem that has multiple use cases in information diffusion, epidemic spreading, and route planning in public transportation. Given a temporal graph G in which each edge associates with a departure time and duration time, and a source vertex s, the Fastest Path Duration (fpd) problem is to compute the journey times from s to all the rest of the vertices in G. The existing multi-core algorithm for fpd by Delling et al. exhibits limited parallelism. In general, many parallel algorithms suffer from doing redundant work while pruning certain computations. Our research focuses on multiple algorithmic ways to avoid redundant work and perform pruning of computations effectively. We introduce three novel gpu-based parallel algorithms for fpd, namely Level Order (lo), Multiple Breadth First Search (mbfs), and Local Work-lists (lw) and implement them on a gpu architecture machine. Our algorithms demonstrate an average speedup of approximately 165 times and a maximum speedup of up to 1383 times over the current state-of-the-art algorithms. This paper provides a comprehensive explanation of various algorithm designs, their optimizations for gpus, and an extensive evaluation of their performance across various temporal graph scenarios.