Simpler and Higher Lower Bounds for Shortcut Sets

We study the well-known shortcut set problem: how much can one decrease the diameter of a directed graph by adding a small set of shortcuts from the transitive closure of the graph.

We provide a variety of lower bounds. First, we vastly simplify the recent construction of Bodwin and Hoppenworth [FOCS 2023] which showed an Ω(n 1/4 ) lower bound for the diameter of a directed unweighted n-node graph after adding O(n) shortcut edges. We highlight that our simplification completely removes the use of the convex sets by Bárány and Larman [Math. Ann. 1998] used in all previous lower bound constructions. Our simplification also removes the need for randomness and further removes some log factors. It allows us to generalize the construction to higher dimensions, which in turn can be used to show the following results:

• There is an Ω(n 1/5 ) lower bound for the diameter of the graph after adding O(m) shortcuts, where m denotes the number of edges in the input graph.

• For all ε > 0, there exists a δ > 0 such that there are n-vertex O(n)-edge graphs G where adding any shortcut set of size O(n 2-ε ) keeps the diameter of G at Ω(n δ ). This improves the sparsity of the constructed graph compared to a known similar result by Hesse [SODA 2003].

• For any integer d ≥ 2, there exists a graph G = (V, E) on n vertices and S ⊆ V with |S| = Θ(n 3/(d+3) ), such that when adding O(n) or O(m) shortcuts, the sourcewise diameter (the largest distance from some vertex in S to some reachable vertex in the graph) is Ω(|S| 1/3 ). This initiates the study of sourcewise diameter in the setting of the shortcut set problem; previously, the study of the sourcewise variant is popular in a wide variety of related problems such as spanners and distance preservers. Complementing this lower bound result, we also provide an upper bound: we show that, we can reduce the sourcewise diameter to O( |S|) by adding O(n) shortcut edges.