Finding Short Paths on Simple Polytopes
This work addresses fundamental computational geometry and optimization problems, providing hardness results that impact algorithm design for linear programming and polytope analysis, with incremental contributions building on prior open questions.
The authors proved that computing a shortest monotone path to the optimum of a linear program over a simple polytope is NP-hard, resolving a 2022 open question, and also showed that computing the diameter of a simple polytope is NP-hard, resolving a 2003 open problem. On the positive side, they demonstrated that every polytope has a small, simple extended formulation allowing a linear length path to be found in polynomial time.
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.