Approximate Shortest Path and Distance Queries in Networks

Computing shortest paths in graphs is one of the most fundamental and well-studied problems in combinatorial optimization. Numerous real-world applications have stimulated research investigations for more than 50 years. Finding routes in road and public transportation networks is a classical application motivating the study of the shortest path problem. Shortest paths are also sought by routing schemes for computer networks: the transmission time of messages is less when they are sent through a short sequence of routers. The problem is also relevant for social networks: one may more likely obtain a favor from a stranger by establishing contact through personal connections.

This thesis investigates the problem of efficiently computing exact and approximate shortest paths in graphs, with the main focus being on shortest path query processing. Strategies for computing answers to shortest path queries may involve the use of pre-computed data structures (often called distance oracles) in order to improve the query time. Designing a shortest path query processing method raises questions such as: How can these data structures 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 distance oracles applicable to general graphs, the quantitative tradeoff between the storage requirement and the approximation quality is known up to constant factors. For distance oracles that take advantage of the properties of certain classes of graphs, however, the tradeoff is less well understood: for some classes of sparse graphs such as planar graphs, there are data structures that enable query algorithms to efficiently compute distance estimates of much higher precision than what the tradeoff for general graphs would predict. The first main contribution of this thesis is a proof that such data structures cannot exist for all sparse graphs. We prove a space lower bound implying that distance oracles with good precision and very low query costs require large amounts of space. A second contribution consists of space- and time-efficient data structures for a large family of complex networks. We prove that exploiting well-connected nodes yields efficient distance oracles for scale-free graphs. A third contribution is a practical method to compute approximate shortest paths. By means of random sampling and graph Voronoi duals, our method successfully accommodates both highly structured graphs stemming from transportation networks and less structured graphs stemming from complex networks such as social networks.

@phdthesis{SommerThesis,
  author    = {Christian Sommer},
  title     = {Approximate Shortest Path and Distance Queries in Networks},
  school      = {The University of Tokyo},
  year      = {2010},
}