Reviving Thorup's Shortcut Conjecture

We aim to revive Thorup’s conjecture [Thorup, WG’92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph G=(V,E) with m edges, we can add m1+o(1) “shortcut” edges E+ from the transitive closure E* of G so that G+(u,v) ≤ mo(1) for all (u,v)∈ E*, where G+=(V,E∪ E+). The conjecture was refuted by Hesse [Hesse, SODA’03], followed by significant efforts in the last few years to optimize the lower bounds. In this paper we observe that although Hesse refuted the letter of Thorup’s conjecture, his work [Hesse, SODA’03]—and all followup work —does not refute the spirit of the conjecture, which should allow G+ to contain both new (shortcut) edges and new Steiner vertices. Our results are as follows. On the positive side, we present explicit attacks that break all known shortcut lower bounds using Steiner vertices. On the negative side, we rule out ideal m1+o(1)-size, mo(1)-diameter shortcuts whose “thickness” is t=o(logn/loglogn), meaning no path can contain t consecutive Steiner vertices. We propose a candidate hard instance as the next step toward resolving the revised version of Thorup’s conjecture. Finally, we show promising implications. Almost-optimal parallel algorithms for computing a generalization of the shortcut that approximately preserves distances or flows imply almost-optimal parallel algorithms with mo(1) depth for exact shortcut paths and exact maximum flow. The state-of-the-art algorithms have much worse depth of n1/2+o(1) [Rozhoň, Haeupler, Martinsson, STOC’23] and m1+o(1) [Chen, Kyng, Liu, FOCS’22], respectively.