Finding Short Paths on Simple Polytopes
2026-03-05 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors prove that finding the shortest path that moves steadily closer to the best solution in a linear programming problem is very hard (NP-hard). They show this difficulty even applies to simple cases like fractional knapsack problems and to finding the shortest pivot steps in the simplex method. They also prove that computing the maximum distance between any two corners (diameter) of a simple polytope is NP-hard, solving a long-standing open problem. However, they found that there exists a simpler way to represent these shapes so that short paths can be found efficiently.
linear programmingsimple polytopemonotone pathNP-hardsimplex methodfractional knapsackpolyhedral constructionpolytope diameterextended formulationpivot sequence
Authors
Alexander E. Black, Raphael Steiner
Abstract
We prove that computing a shortest monotone path to the optimum of a linear program over a simple polytope is NP-hard, thus resolving a 2022 open question of De Loera, Kafer, and Sanità. As a consequence, finding a shortest sequence of pivots to an optimal basis with the simplex method is NP-hard. In fact, we show this is NP-hard already for fractional knapsack polytopes. By applying an additional polyhedral construction, we show that computing the diameter of a simple polytope is NP-hard, resolving a 2003 open problem by Kaibel and Pfetsch. Finally, on the positive side we show that every polytope has a small, simple extended formulation for which a linear length path may be found between any pair of vertices in polynomial time building upon a result of Kaibel and Kukharenko.