Information Bounds Are Weak in the Shortest Distance Problem

ASSTRACT. In the all-pair shortest distance problem, one computes the matrix D = (du), where dq is the minimum weighted length of any path from vertex i to vertexj in a directed complete graph with a weight on each edge. In all the known algorithms, a shortest path p, ~ achieving di./is also implicitly computed. In fact, logs(f (n)) is an information-theoretic lower bound, wheref(n) is the total number of distinct patterns (Po) for n-vertex graphs. As f(n) potentially can be as large as 2":', it would appear possible that a nontrivial lower bound can be derived this way in the decision tree model. The characterization and enumeration of realizable patterns is studied, and it is shown thatf(n) < C "~. Thus no lower bound greater than Cn 2 can be derived from this approach. It is proved as a corollary that the Triangular polyhedron T ~"~, defined in E ¢~' ~ by d,j> 0 and the triangle inequalities d~j + dik> d,k, has at most C" ' faces of all dimensions, thus resolving an open question in a similar information bound approach to the shortest distance problem.