pith. machine review for the scientific record. sign in

arxiv: 2603.05482 · v2 · submitted 2026-03-05 · 💻 cs.DS · math.CO· math.OC

Recognition: 2 theorem links

· Lean Theorem

Finding Short Paths on Simple Polytopes

Alexander E. Black , Raphael Steiner
Authors on Pith no claims yet

Pith reviewed 2026-05-15 15:05 UTC · model grok-4.3

classification 💻 cs.DS math.COmath.OC
keywords NP-hardnesssimple polytopesmonotone pathssimplex methodpolytope diameterextended formulationslinear programmingfractional knapsack
0
0 comments X

The pith

Computing shortest monotone paths to the optimum on simple polytopes is NP-hard

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that finding the shortest monotone path from a vertex to the optimal solution of a linear program over a simple polytope is NP-hard. This holds already for fractional knapsack polytopes and implies that computing the shortest pivot sequence to an optimal basis in the simplex method is NP-hard. The same techniques establish that computing the diameter of a simple polytope is NP-hard. On the positive side, the authors construct small simple extended formulations for any polytope in which a linear-length path between any pair of vertices can be found in polynomial time.

Core claim

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. As a consequence, finding a shortest sequence of pivots to an optimal basis with the simplex method is NP-hard already for fractional knapsack polytopes. We show that computing the diameter of a simple polytope is NP-hard, resolving a 2003 open problem. 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.

What carries the argument

Polyhedral reductions from known NP-hard problems that preserve simplicity of the polytopes and monotonicity of paths, together with an additional construction that yields small simple extended formulations admitting short paths.

If this is right

  • Shortest pivot sequences to an optimal basis in the simplex method are NP-hard to compute even on simple polytopes.
  • Computing the diameter of a simple polytope is NP-hard.
  • Small simple extended formulations exist for every polytope in which linear-length vertex-to-vertex paths can be found in polynomial time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • In practice the simplex method will often need heuristics or approximations rather than exact shortest-path information on worst-case simple polytopes.
  • The positive extended-formulation result indicates that adding a modest number of variables can convert hard path problems into polynomially solvable ones.
  • The hardness for diameter suggests that many other shortest-path or distance questions on simple polytopes are likely intractable.

Load-bearing premise

The reductions from known NP-hard problems correctly preserve simplicity of the polytopes and monotonicity of the paths in the constructed instances.

What would settle it

Discovery of a polynomial-time algorithm that computes a shortest monotone path to the LP optimum on every simple polytope, or on every fractional knapsack polytope, would falsify the NP-hardness result.

Figures

Figures reproduced from arXiv: 2603.05482 by Alexander E. Black, Raphael Steiner.

Figure 1
Figure 1. Figure 1: Depicted are the four different ways a hyperplane can slice two edges of a 2-face of a hypercube, which gives rise to the notions (c), (d), (e), and (f) of adjacency in Lemma 2.3. Note there are truly six ways this can occur, but the remaining two correspond to swapping i and j for edges of type (d) and (e). Lemma 2.2. The graph of Pb has vertex set V1 ∪ V2, where V1 = ( eS [PITH_FULL_IMAGE:figures/full_f… view at source ↗
Figure 2
Figure 2. Figure 2: Depicted is the silo construction in d = 3 dimensions in the normal fan of the polytope. Namely, the outer triangle corresponds to the normal cone of the vertex being cut off. We visualize this as a triangle by slicing the cone with a plane. Then the siloing subdivides that slice. The basis exchange graph corresponds to the dual graph of the triangulation. In this picture it is already visible that two cel… view at source ↗
Figure 3
Figure 3. Figure 3: Depicted is the graph Gd for d = 5. Vertices of the same height (i.e., second coordinate) are pairwise adjacent. Otherwise, there is an edge from a vertex to the first vertex above it and below it that is in the graph. result here, which we however have no access to. In fact, we leave finding such an APX-hardness result as an open problem in Section 5. Due to this subtle technical difficulty, we must be ca… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proves 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 of De Loera, Kafer, and Sanità; this holds already for fractional knapsack polytopes and implies NP-hardness of finding shortest simplex pivot sequences. It further shows that computing the diameter of a simple polytope is NP-hard, resolving a 2003 open problem of Kaibel and Pfetsch. On the positive side, every polytope admits a small simple extended formulation in which a linear-length path between any pair of vertices can be found in polynomial time, building on Kaibel and Kukharenko.

Significance. If the reductions and constructions are correct, the results are significant: they settle two longstanding open questions in polyhedral combinatorics and the complexity of linear programming. The explicit reductions from established NP-hard problems (including to fractional knapsack polytopes) and the polynomial-time constructive positive result on extended formulations are strengths that provide both negative and positive algorithmic insights.

major comments (2)
  1. [the main hardness reduction for monotone paths] In the reduction establishing NP-hardness for shortest monotone paths on fractional knapsack polytopes (the core construction resolving the 2022 question), the argument that the resulting polytope remains simple must be verified vertex-by-vertex; if any constructed vertex has degree exceeding the dimension, the simplicity assumption fails and the hardness claim does not apply to simple polytopes.
  2. [the polyhedral construction for diameter hardness] In the lifting construction that extends the monotone-path hardness to diameter hardness, the added vertices and facets must be shown not to create polynomial-length shortcuts; without an explicit bound on the new diameter in terms of the original instance, the reduction may not preserve NP-hardness.
minor comments (2)
  1. [Abstract] The LaTeX rendering of 'Sanit`a' in the abstract should be corrected to the proper accented form 'Sanità'.
  2. [the extended-formulation section] The positive result should include a brief self-contained statement of the Kaibel-Kukharenko theorem being invoked, to make the polynomial-time path construction fully readable without external lookup.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and will incorporate clarifications in the revised version to strengthen the proofs.

read point-by-point responses

  1. Referee: In the reduction establishing NP-hardness for shortest monotone paths on fractional knapsack polytopes (the core construction resolving the 2022 question), the argument that the resulting polytope remains simple must be verified vertex-by-vertex; if any constructed vertex has degree exceeding the dimension, the simplicity assumption fails and the hardness claim does not apply to simple polytopes.

    Authors: We thank the referee for this observation. The construction in Section 3 defines the polytope via a set of inequalities where each vertex is incident to exactly d tight constraints in dimension d, by design of the fractional knapsack structure and the added gadgets. To make this fully rigorous, we will add a dedicated lemma in the revision that classifies all vertex types (original knapsack vertices and those from the reduction) and verifies their degrees explicitly via the incidence matrix, confirming no vertex exceeds degree d. This does not change the reduction but provides the requested verification. revision: yes

  2. Referee: In the lifting construction that extends the monotone-path hardness to diameter hardness, the added vertices and facets must be shown not to create polynomial-length shortcuts; without an explicit bound on the new diameter in terms of the original instance, the reduction may not preserve NP-hardness.

    Authors: We agree that an explicit bound strengthens the argument. In the proof of the diameter hardness result (Section 4), we already establish that any path in the lifted polytope using new vertices or facets must cross between the original and lifted components in a way that adds at least a linear number of steps proportional to the original monotone path length. We will revise to include an explicit proposition stating that the diameter of the lifted polytope is at most 2 times the original diameter plus O(d), where d is the dimension. This bound is polynomial in the input size and preserves the NP-hardness of the decision problem. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central claims consist of NP-hardness results obtained via explicit polyhedral reductions from established NP-hard problems (fractional knapsack polytopes) that preserve simplicity and monotonicity, followed by a positive extended-formulation result constructed from the external Kaibel-Kukharenko theorem. No step reduces by definition to its own inputs, renames a fitted quantity as a prediction, or relies on a load-bearing self-citation chain; the derivation remains independent of the target results and is externally falsifiable through the cited reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Claims rest on standard complexity-theoretic assumptions and specific polyhedral reduction constructions from known hard problems; no free parameters or invented entities.

axioms (1)
  • standard math Standard assumption that P ≠ NP for interpreting NP-hardness as intractability
    Implicit in all NP-hardness statements to conclude no polynomial-time algorithm exists

pith-pipeline@v0.9.0 · 5439 in / 1158 out tokens · 62642 ms · 2026-05-15T15:05:17.878795+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Finding Shortest Reconfiguration Sequences on Independent Set Polytopes

    cs.DS 2026-04 unverdicted novelty 8.0

    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.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages · cited by 1 Pith paper

  1. [1]

    Adler, C

    I. Adler, C. Papadimitriou, and A. Rubinstein,On simplex pivoting rules and complexity theory, International Conference on Integer Programming and Combinatorial Optimization, Springer, 2014, pp. 13–24. 1

    work page 2014

  2. [2]

    Aichholzer, J

    O. Aichholzer, J. Cardinal, T. Huynh, K. Knauer, T. Mütze, R. Steiner, and B. Vogtenhuber,Flip distances between graph orientations, Algorithmica83(2021), no. 1, 116–143. 2

    work page 2021

  3. [3]

    Amenta and G

    N. Amenta and G. Ziegler,Deformed products and maximal shadows, Contemporary Math.223(1998), 57–90. 1

    work page 1998

  4. [4]

    Avis and V

    D. Avis and V. Chvátal,Notes on Bland’s pivoting rule, Polyhedral Combinatorics, Springer, 1978, pp. 24–34. 1

    work page 1978

  5. [5]

    Black,Exponential lower bounds for many pivot rules for the simplex method, Mathematical Programming (2026)

    A. Black,Exponential lower bounds for many pivot rules for the simplex method, Mathematical Programming (2026). 1, 4

    work page 2026

  6. [6]

    Black, C

    A. Black, C. Nöbel, and R. Steiner,Short circuit walks in fixed dimension, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2026, pp. 563–573. 2

    work page 2026

  7. [7]

    Borgwardt,The simplex method: A probabilistic analysis, vol

    K. Borgwardt,The simplex method: A probabilistic analysis, vol. 1, Springer-Verlag, Berlin, 1987. 1

    work page 1987

  8. [8]

    Borgwardt, W

    S. Borgwardt, W. Grewe, S. Kafer, J. Lee, and L. Sanità,On the hardness of short and sign-compatible circuit walks, Discrete Applied Mathematics367(2025), 129–149. 2

    work page 2025

  9. [9]

    Cardinal and R

    J. Cardinal and R. Steiner,Inapproximability of shortest paths on perfect matching polytopes, Mathematical Programming210(2025), no. 1, 147–163. 2

    work page 2025

  10. [10]

    ,Shortest paths on polymatroids and hypergraphic polytopes, Combinatorial Theory5(3)(2025). 2, 4

    work page 2025

  11. [11]

    De Loera, S Kafer, and L

    J. De Loera, S Kafer, and L. Sanità,Pivot rules for circuit-augmentation algorithms in linear optimization, SIAM Journal on Optimization32(2022), no. 3, 2156–2179. 2

    work page 2022

  12. [12]

    Disser, O

    Y. Disser, O. Friedmann, and A. Hopp,An exponential lower bound for Zadeh’s pivot rule, Mathematical Pro- gramming (2022). 1

    work page 2022

  13. [13]

    Disser, G

    Y. Disser, G. Loho, M. Maat, and N. Mosis,Lower bounds for ranking-based pivot rules, arXiv preprint arXiv:2512.16684 (2025). 1

    work page arXiv 2025

  14. [14]

    Disser and N

    Y. Disser and N. Mosis,A Unified Worst Case for Classical Simplex and Policy Iteration Pivot Rules, 34th International Symposium on Algorithms and Computation (ISAAC 2023) (Dagstuhl, Germany) (Satoru Iwata and Naonori Kakimura, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 283, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 20...

    work page 2023

  15. [15]

    Disser and M

    Y. Disser and M. Skutella,The simplex algorithm is np-mighty, ACM Transactions on Algorithms (TALG)15 (2018), no. 1, 1–19. 1

    work page 2018

  16. [16]

    Dorfer,Flip distance of triangulations of convex polygons / rotation distance of binary trees is np-complete,

    J. Dorfer,Flip distance of triangulations of convex polygons / rotation distance of binary trees is np-complete,

    work page

  17. [17]

    Fearnley and R

    J. Fearnley and R. Savani,The complexity of the simplex method, Proceedings of the forty-seventh annual ACM symposium on Theory of computing, 2015, pp. 201–208. 1

    work page 2015

  18. [18]

    O. Friedmann,A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games, Proceedings of 15th International Conference on Integer Programming and Combinatorial Optimization (Oktay Günlük and Gerhard J. Woeginger, eds.), Springer, 2011, pp. 192–206. 1

    work page 2011

  19. [19]

    Friedmann, T

    O. Friedmann, T. Hansen, and U. Zwick,Subexponential lower bounds for randomized pivoting rules for the simplex algorithm, Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 2011, pp. 283–292. 1

    work page 2011

  20. [20]

    Frieze and S

    A. Frieze and S. Teng,On the complexity of computing the diameter of polytope, Comput. Complex.4(1994), no. 3, 207–219. 2, 4, 16

    work page 1994

  21. [21]

    Goldfarb,Worst case complexity of the shadow vertex simplex algorithm, preprint, Columbia University (1983)

    D. Goldfarb,Worst case complexity of the shadow vertex simplex algorithm, preprint, Columbia University (1983). 1

    work page 1983

  22. [22]

    Goldfarb and W

    D. Goldfarb and W. Sit,Worst case behavior of the steepest edge simplex method, Discrete Applied Mathematics 1(1979), no. 4, 277–285. 1

    work page 1979

  23. [23]

    Hansen and U

    T. Hansen and U. Zwick,An improved version of the random-facet pivoting rule for the simplex algorithm, Pro- ceedings of the forty-seventh annual ACM symposium on Theory of computing, 2015, pp. 209–218. 1

    work page 2015

  24. [24]

    Holt and V

    F. Holt and V. Klee,Many polytopes meeting the conjectured hirsch bound, Discrete & Computational Geometry 20(1998), no. 1, 1–17. 4

    work page 1998

  25. [25]

    T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto,Shortest reconfiguration of perfect matchings via alternating cycles, SIAM Journal on Discrete Mathematics36(2022), no. 2, 1102–1123. 2 30

    work page 2022

  26. [26]

    Jeroslow,The simplex algorithm with the pivot rule of maximizing criterion improvement, Discrete Mathematics 4(1973), no

    R. Jeroslow,The simplex algorithm with the pivot rule of maximizing criterion improvement, Discrete Mathematics 4(1973), no. 4, 367–377. 1

    work page 1973

  27. [27]

    Kaibel and K

    V. Kaibel and K. Kukharenko,Rock extensions with linear diameters, SIAM Journal on Discrete Mathematics38 (2024), no. 4, 2982–3003. 5, 27

    work page 2024

  28. [28]

    Kaibel and M

    V. Kaibel and M. Pfetsch,Some algorithmic problems in polytope theory, Algebra, geometry and software systems, Springer, 2003, pp. 23–47. 3

    work page 2003

  29. [29]

    Kalai,A subexponential randomized simplex algorithm, Proceedings of the twenty-fourth annual ACM sympo- sium on Theory of computing, 1992, pp

    G. Kalai,A subexponential randomized simplex algorithm, Proceedings of the twenty-fourth annual ACM sympo- sium on Theory of computing, 1992, pp. 475–482. 1

    work page 1992

  30. [30]

    Karp,Reducibility among combinatorial problems, 50 Years of Integer Programming 1958-2008: from the Early Years to the State-of-the-Art, Springer, 2009, pp

    R. Karp,Reducibility among combinatorial problems, 50 Years of Integer Programming 1958-2008: from the Early Years to the State-of-the-Art, Springer, 2009, pp. 219–241. 6

    work page 1958

  31. [31]

    Klee and G

    V. Klee and G. Minty,How good is the simplex algorithm, Inequalities : III : proceedings of the 3rd Symposium on inequalities (1972), 159–175. 1

    work page 1972

  32. [32]

    Kukharenko,Short paths for the simplex algorithm, Ph.D

    K. Kukharenko,Short paths for the simplex algorithm, Ph.D. thesis, Dissertation, Magdeburg, Otto-von-Guericke- Universität Magdeburg, 2025, 2025. 5

    work page 2025

  33. [33]

    Matoušek, M

    J. Matoušek, M. Sharir, and E. Welzl,A subexponential bound for linear programming, Algorithmica16(1996), no. 4-5, 498–516. 1

    work page 1996

  34. [34]

    Murty,Computational complexity of parametric linear programming, Mathematical programming19(1980), no

    K. Murty,Computational complexity of parametric linear programming, Mathematical programming19(1980), no. 1, 213–219. 1

    work page 1980

  35. [35]

    Natura,Circuit diameter of polyhedra is strongly polynomial, arXiv preprint arXiv:2602.06958 (2026)

    B. Natura,Circuit diameter of polyhedra is strongly polynomial, arXiv preprint arXiv:2602.06958 (2026). 5

    work page arXiv 2026

  36. [36]

    Nöbel and R

    C. Nöbel and R. Steiner,Complexity of polytope diameters via perfect matchings, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2025, pp. 2234–2251. 2

    work page 2025

  37. [37]

    2, 109–129

    J.Orlin,A polynomial time primal network simplex algorithm for minimum cost flows, MathematicalProgramming 78(1997), no. 2, 109–129. 1

    work page 1997

  38. [38]

    Sanità,The diameter of the fractional matching polytope and its hardness implications, 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 2018, pp

    L. Sanità,The diameter of the fractional matching polytope and its hardness implications, 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 2018, pp. 910–921. 2, 3

    work page 2018

  39. [39]

    Santos,A counterexample to the Hirsch conjecture, Annals of Mathematics (2012), 383–412

    F. Santos,A counterexample to the Hirsch conjecture, Annals of Mathematics (2012), 383–412. 1

    work page 2012

  40. [40]

    Sleator, R

    D. Sleator, R. Tarjan, and W. Thurston,Rotation distance, triangulations, and hyperbolic geometry, Proceedings of the eighteenth annual ACM symposium on Theory of computing, 1986, pp. 122–135. 3

    work page 1986

  41. [41]

    Spielman and S

    D. Spielman and S. Teng,Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM (JACM)51(2004), no. 3, 385–463. 1

    work page 2004

  42. [42]

    Lasse Wulf,Computing the polytope diameter is even harder than np-hard (already for perfect matchings), to appear in FOCS 2025 (2025). 2, 3

    work page 2025