Institution: Stanford University, Department of Computer Science

Title: Information bounds are weak in the shortest distance problem

Author: Graham, Ronald L.

Author: Yao, Andrew C.

Author: Yao, F. Frances

Date: September 1978

Abstract: In the all-pair shortest distance problem, one computes the matrix D = ($d_{ij}$) where $d_{ij}$ is the minimum weighted length of any path from vertex i to vertex j in a directed complete graph with a weight on each edge. In all the known algorithms, a shortest path $p_{ij}$ achieving $d_{ij}$ is also implicitly computed. In fact, $\log_3$ f(n) is an information-theoretic lower bound where f(n) is the total number of distinct patterns ($p_{ij}$) for n-vertex graphs. As f(n) potentially can be as large as $2^{n^3}$, it is hopeful that a non-trivial lower bound can be derived this way in the decision tree model. We study the characterization and enumeration of realizable patterns, and show that f(n) $\leq C^{n^2}$. Thus no lower bound greater than C$n^2$ can be derived from this approach. We prove as a corollary that the Triangular polyhedron $T^{(n)}$, defined in $E^{(n\choose 2)}$ by $d_{ij} \geq 0$ and the triangle inequalities $d_{ij} + d_{jk} \geq d_{ik}$, has at most $C^{n^2}$ faces of all dimensions, thus resolving an open question in a similar information bound approach to the shortest distance problem.

http://i.stanford.edu/pub/cstr/reports/cs/tr/78/670/CS-TR-78-670.pdf