The Structure of Unique Shortest Paths in Graphs

Lots of problems in computer science theory, such as All Pairs Shortest Paths (APSP), concern shortest paths in real-weighted graphs. In this setting, we may conveniently assume without loss of generality that there is a unique shortest path between each pair of nodes (e.g. because we may break ties by randomly perturbing edge weights). But what exactly does this assumption buy us? What structural constraints must be obeyed by unique shortest paths? For example, it is currently open to determine the solution space of APSP: which systems of paths can possibly be the correct output to an APSP instance (with perturbed edge weights), or which can we discard a priori before even inspecting the input graph?

In this talk, we will answer these questions by fully characterizing the set of path systems that can possibly appear as unique shortest paths in some graph. Our characterization theorem is based on a new connection between graph metrics and certain boundary operators used in some recent graph homology theories. This connection also leads to a principled topological understanding of some of the popular algebraic tricks currently used in the literature on shortest paths. (However, no prior knowledge of topology, homology, etc will be needed to understand this talk.)