The diameters of network-flow polytopes satisfy the Hirsch conjecture (Q1785200): Difference between revisions

The authors present a final solution to the problem of finding the exact bound on the diameter of a network-flow polytope. Their main result states that the diameters of all network-flow polytopes satisfy the Hirsch conjecture and there are network-flow polytopes, for which the Hirsch bound is tight. In particular, the diameter of a network with \(n\) nodes and \(m\) arcs does not exceed the linear bound \(m+n-1\). To prove this result, the authors show first that the diameter of an \(N_{1}\times N_{2}\)-transportation polytope is bounded above by \(N_{1}+N_{2}-1-\mu\), where \(\mu\) is the number of critical pairs of the transportation polytope. Then it is shown that the truth of the Hirsch conjecture in case of \(N_{1}\times N_{2}\)-transportation polytopes and their faces imply the main result of this paper. An algorithm, which defines a walk from an initial tree to a final tree on the 1-skeleton of a non-degenerate transportation polytope is described. The walk is fully defined by the corresponding concrete finite sequence of trees, which has at most \(N_{1}+N_{2}-1-\mu\) steps.