The diameter of an undirected graph can be reduced by adding additional edges (shortcuts). Adding O(n) random edges to a graph with n vertices will, with high probablility, reduce the diameter to O(log n). This is the theory of expander graphs, which has been instrumental to many recent results in theoretical computer science.
Can the same be done with a directed graph? We introduce the additional restriction that our shortcut edges may only span vertices that are already connected by a directed path. Thus the shortcut edges are edges from the transitive closure of the graph, and there is a path from s to t in the shortcutted graph if and only if there is a path from s to t in the original graph. We have found a counterexample to a conjecture by Thorup that the diameter of a directed graph with n vertices and m edges can be reduced to polylog( n ) by the addition of O(m) shortcuts.
We construct a directed graph with n vertices, n18/17 edges, and
diameter n1/17 that requires the addition of O(m n1/17)
shortcuts to reduce
its diameter. This construction extends to graphs with n1+epsilon
edges that require n2-epsilon shortcuts. This extension depends on
recent results by Barany on the maximum number of vertices of a convex
body of volume V on the d-dimensional integer lattice.
Last modified 30 September 2002