KAIST Discrete Math Seminar

We discuss how to efficiently compute shortest and approximate shortest paths in graphs, thereby focusing on shortest path query processing. The algorithm computing (approximate) shortest path queries is allowed to access a pre-computed data structure (often called distance oracle) in order to improve the query time. Several questions regarding such data structures are of particular interest: How can they be computed efficiently? What amount of storage is necessary? How much improvement of the query time is possible? How good is the approximation quality of the query result? What are the tradeoffs between pre-computation time, storage, query time, and approximation quality?

For general dense graphs, the tradeoff between the storage requirement and the approximation quality is known up to constant factors. We discuss both the lower and the upper bound (by Thorup and Zwick). For specific types of sparse graphs, however, the exact tradeoff is not known; the general tradeoff can be improved: there are special data structures of a certain size that enable query algorithms to return distances of higher quality than what the general tradeoff would predict. We outline the state of the art of distance oracles for planar graphs and other classes of sparse graphs. We then prove that this improvement for some classes of sparse graphs cannot be extended to all sparse graphs: there is a three-way relationship between space, query time, and approximation quality for general sparse graphs. If time permits, we also cover space- and time-efficient data structures for certain complex networks with power-law degree sequences.

Joint work with Wei Chen, Shinichi Honiden, Michael Houle, Ken-ichi Kawarabayashi, Shang-Hua Teng, Elad Verbin, Yajun Wang, Martin Wolff, and Wei Yu.