Highway Dimension and Provably Efficient Shortest Path Algorithms

Computing driving directions has motivated many shortest path algorithms based on preprocessing. Given a graph, the preprocessing stage computes a modest amount of auxiliary data, which is then used to speed up on-line queries. The best algorithms have storage overhead comparable to the graph size and answer queries very fast, while examining a small fraction of the graph. In this paper we complement the experimental evidence with the first rigorous proofs of efficiency for some of the algorithms developed over the past decade. We define highway dimension, which strengthens the notion of doubling dimension.Under the assumption that the highway dimension is low (at most polylogarithmic in the graph size), we show that, for some algorithms, preprocessing can be implemented in polynomial time, the resulting auxiliary data increases the storage requirements by a polylogarithmic factor, and queries run in polylogarithmic time. This gives a unified explanation for the performance of several seemingly different approaches. Our best bounds are based on a result that may be of independent interest. We show that unique shortest paths induce set systems of low VC-dimension, which makes them combinatorially simple.