Shortest reconfiguration sequences for independent sets under connected symmetric difference are NP-hard on planar and split graphs but polynomial-time solvable on block graphs, cographs, and bipartite chain graphs.
Finding Short Paths on Simple Polytopes
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
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\`a. 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.
years
2026 2representative citing papers
Frieze and Teng's 1994 ILP formulation for Exact Partition can yield degenerate polytopes; the note supplies explicit small examples and observes that a simple preprocessing step avoids them for complexity applications.
citing papers explorer
-
Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
Shortest reconfiguration sequences for independent sets under connected symmetric difference are NP-hard on planar and split graphs but polynomial-time solvable on block graphs, cographs, and bipartite chain graphs.
-
A note on the exact partition polytope of Frieze and Teng
Frieze and Teng's 1994 ILP formulation for Exact Partition can yield degenerate polytopes; the note supplies explicit small examples and observes that a simple preprocessing step avoids them for complexity applications.