Reducing Shortcut and Hopset Constructions to Shallow Graphs

We introduce a blackbox framework that simplifies all known parallel algorithms with near-linear work for single-source reachability and shortest paths in directed graphs. Specifically, existing reachability algorithms rely on constructing shortcuts; our blackbox allows these algorithms that construct shortcuts with hopbound \(h\) to assume the input graph \(G\) is “shallow”, meaning if vertex \(s\) can reach vertex \(t\), it can do so in approximately \(h\) hops. This assumption significantly simplifies shortcut construction [Fin18, JLS19], resulting in simpler parallel reachability algorithms. Furthermore, our blackbox extends naturally to simplify parallel algorithms for constructing hopsets and, consequently, for computing shortest paths [CFR20, CF23, RHM+23].