The <i>d</i>-Step Conjecture and Its Relatives

Abstract

The d-step conjecture arose from an attempt to understand the computational complexity of edge-following algorithms for linear programming, such as the simplex algorithm. It can be stated in terms of diameters of graphs of convex polytopes, in terms of the existence of nonrevisiting paths in such graphs, in terms of an exchange process for simplicial bases of a vector space, and in terms of matrix pivot operations. First formulated by W. M. Hirsch in 1957, the conjecture remains unsettled, though it has been proved in many special cases and counterexamples have been found for slightly stronger conjectures. If the conjecture is false, as we believe to be the case, then finding a counterexample will be merely a small first step in the line of investigation related to the conjecture. This report summarizes what is known about the d-step conjecture and its relatives. A considerable amount of new material is included, but it does not seem to come close to settling the conjecture. Of special interest is the first example of a polytope that is not vertex-decomposable, showing that a certain natural approach to the conjecture will not work. Also significant are the quantitative relations among the lengths of paths associated with various forms of the conjecture.