Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness

All parallel algorithms for directed reachability and shortest paths crucially rely on efficient shortcut constructions. These constructions find directed paths and shortcut them by adding edges, with the goal to reduce the diameter of the graph. A long sequence of works has studied (efficient) shortcut constructions as well as impossibility results on the best diameter and therefore the best parallelism that can be achieved via this approach.

This paper introduces a new conceptual tool for this line of research in the form of a simple and natural structural criterion: A shortcut H for a graph G is certified if for any shortcut edge (u, v) ∈ H, there exists a vertex w such that the edges (u, w) and (w, v) are also in G ∪ H.

We show that this criterion captures constructiveness in the following sense: A shortcut H can be constructed in t time by repeatedly spending l time on shortcutting a path of length l, if and only if, there exists a certified shortcut H′ ⊇ H of size Õ(t). Furthermore, all known shortcut constructions with efficient algorithms can be extended to produce certified shortcuts of size Õ(m). On the other hand, for shortcut constructions for which attempts to find efficient implementations have failed, we can show that this is impossible.

We also obtain stronger diameter lower bounds for certified shortcuts and hopsets. For example, no certified shortcut construction with almost-linear size can reduce a graph’s diameter below n^{1/4−o(1)}. This seems to be the best bound one can hope for with current techniques.