Directed graphs requiring large numbers of shortcuts

A conjecture by Thorup is that the diameter of a directed graph with n vertices and m edges can be reduced to (log n) O(1) in by adding O(m) edges [3]. We give a counterexample to this conjecture. We construct a graph G requiring the addition of Ω(mn 1/17) edges to reduce its diameter below Θ(n 1/17). By extending the construction to higher dimensions, we construct graphs with n 1+ǫ edges that require the addition of Ω(n 2−ǫ) edges to reduce their diameter. These constructions yield time-space tradeoffs in lower bounds for transitive closure queries in a certain computational model.