Nöbel and Steiner (SODA 2025 / Mathematical Programming 2026; arXiv 2404.04158, v1 titled 'Hardness of circuit and monotone diameters of polytopes') proved that computing the circuit diameter and the monotone (circuit) diameter of a polytope given in halfspace description is strongly NP-hard, and explicitly left two issues open: the circuit diameter conjecture of Borgwardt, Finhold and Hemmecke — whether every polytope P⊆RdP\subseteq\mathbb{R}^d with nn facets satisfies cdiam(P)≤n−d\mathrm{cdiam}(P)\le n-d, the Hirsch-type bound whose combinatorial analogue was disproved by Santos — and whether their hardness could be strengthened to inapproximability. Later work resolved large parts of both: Wulf (FOCS 2025) proved that computing the (circuit) diameter of the bipartite perfect matching polytope is Π2p\Pi^p_2-complete and inapproximable within (1+ε)(1+\varepsilon) for some ε>0\varepsilon>0 unless P=NP\mathrm{P}=\mathrm{NP}, answering the inapproximability question for the ordinary (circuit) diameter; Natura (2026) proved cdiam(P)=O(m2log⁡m)\mathrm{cdiam}(P)=O(m^2\log m) for standard-form polyhedra, settling the circuit analogue of the polynomial Hirsch conjecture. This record states the surviving open core: the sharp linear bound cdiam(P)≤n−d\mathrm{cdiam}(P)\le n-d, and the approximability status of monotone-diameter computation (together with the question of whether the ordinary circuit diameter cdiam(P)\mathrm{cdiam}(P) admits any constant-factor approximation), both of which remain open.

Background

A polytope P⊆RdP\subseteq\mathbb{R}^d given by a rational system Ax≤bAx\le b of nn inequalities has a graph (its 1-skeleton) whose vertices and edges support the simplex method for linear programming. The combinatorial diameter diam(P)\mathrm{diam}(P) is the largest, over all pairs of vertices, of the length of a shortest edge path between them; it lower bounds the number of pivots that any simplex pivot rule may need in the worst case. The 1957 Hirsch conjecture asserted diam(P)≤n−d\mathrm{diam}(P)\le n-d; Santos disproved it in 2012, but whether diam(P)\mathrm{diam}(P) is bounded by any polynomial in nn and dd (the polynomial Hirsch conjecture) remains open, with a quasipolynomial bound of Kalai and Kleitman the best general result. Because the simplex method always follows paths along which the objective cTxc^{T}x does not increase, an even sharper parameter is the monotone diameter mdiam(P)\mathrm{mdiam}(P): the maximum over objectives cc and vertices xx of the length of a shortest cc-monotone edge walk from xx to a cc-optimal vertex.

Circuits generalize edge directions. For a polyhedron P={x:Ax=b,x≥0}P=\{x:Ax=b,x\ge 0\}, its circuits are the support-minimal nonzero solutions of the homogeneous system Ax=0Ax=0 — a finite set of directions gg such that a circuit move from a feasible point xx goes to x+αgx+\alpha g with α>0\alpha>0 chosen maximal subject to x+αg∈Px+\alpha g\in P. For a polytope in halfspace description Ax≤bAx\le b (the form in which the conjecture below is stated), a circuit is a nonzero gg such that AgAg has inclusion-wise minimal support among all vectors AyAy with y≠0y\ne 0; in either form the circuits depend only on the constraint matrix, not on the right-hand side. A circuit walk is a sequence of such moves; it need not stay on vertices. The circuit diameter cdiam(P)\mathrm{cdiam}(P), introduced by Borgwardt, Finhold and Hemmecke in 2015, is the maximum over vertex pairs of the shortest circuit-walk length; since every edge move is a circuit move, cdiam(P)≤diam(P)\mathrm{cdiam}(P)\le\mathrm{diam}(P). It lower bounds the iteration count of circuit augmentation algorithms, a family of linear-programming algorithms that generalizes the simplex method by moving along circuits rather than only edges; the existence of a strongly polynomial circuit augmentation scheme matching the circuit diameter would resolve the long-standing question of a strongly polynomial algorithm for linear programming (Smale's ninth problem). The monotone circuit diameter mcdiam(P)\mathrm{mcdiam}(P) is defined analogously via cc-monotone circuit walks.

The circuit diameter conjecture (Borgwardt–Finhold–Hemmecke, 2015) asserts that the Hirsch bound survives the relaxation: every polytope P⊆RdP\subseteq\mathbb{R}^d with nn facets satisfies cdiam(P)≤n−d\mathrm{cdiam}(P)\le n-d. Recent work describes it as the main open problem of this area. The supporting evidence includes: the conjecture holds for dual transportation polyhedra (the feasible regions of the duals of transportation problems, a classical family of network-flow polytopes) and for many combinatorial polytopes (Kafer–Pashkovich–Sanità); the circuit analogues of the d-step conjecture (any two vertices of a dd-dimensional polytope at combinatorial distance dd lie on a common face of dimension at most 2d2d) and of the non-revisiting conjecture (any two vertices are joined by a path that never returns to a facet it has left) imply it (Borgwardt–Stephen–Yusun); and none of the known counterexamples to the Hirsch conjecture — the bounded Santos-type counterexamples, Todd's monotone counterexample, or the Klee–Walkup counterexample to the unbounded Hirsch conjecture — transfers to the circuit setting (Borgwardt–Stephen–Yusun; Black–Borgwardt–Brugger). Until 2026 the best general upper bounds depended on numerical data of the constraint matrix through circuit imbalance measures (parameters capturing the spread of entry magnitudes within a single circuit; Dadush–Koh–Natura–Végh).

On the computational side, Frieze and Teng (1994) proved that computing diam(P)\mathrm{diam}(P) exactly is weakly NP-hard and asked whether the corresponding decision problem might be complete for the second level of the polynomial hierarchy, Π2p\Pi^p_2. Sanità (FOCS 2018) proved strong NP-hardness of computing the diameter of the fractional matching polytope, and showed that finding a pair of vertices at maximum shortest-path distance in it is APX-hard. Nöbel and Steiner then proved that computing the (monotone) circuit diameter of a polytope in halfspace description is strongly NP-hard — even for the perfect matching polytope PGP_G of a bipartite graph GG, a {0,1}\{0,1\}-polytope whose constraint matrix is totally unimodular (all its square subdeterminants lie in {0,±1}\{0,\pm 1\}) and on which circuit moves and edge moves coincide — and likewise that computing the diameter and the monotone diameter of such polytopes is NP-hard. In their paper (Conjecture 3 of arXiv v1, Conjecture 6 of the published version) the circuit diameter conjecture is stated as remaining open, and they remark that strengthening their hardness theorems (Theorems 8 and 9 of arXiv v1, Theorems 2 and 3 of the published version) to an inapproximability result for the diameter 'would be quite interesting, but this seems to be outside the reach of the methods used in our proof'.

Problem Statement

The problem consists of two linked questions, together forming the surviving open core of the diameter questions that Nöbel and Steiner's hardness theorems left unresolved.

(1) The circuit diameter conjecture (the Hirsch-type linear bound). Prove that every polytope P⊆RdP\subseteq\mathbb{R}^d with nn facets satisfies cdiam(P)≤n−d\mathrm{cdiam}(P)\le n-d, where cdiam(P)\mathrm{cdiam}(P) is the maximum over pairs of vertices of the minimum length of a circuit walk (a sequence of maximal feasible steps along the circuits, i.e. the support-minimal directions, of PP); or exhibit an explicit counterexample — a polytope with cdiam(P)>n−d\mathrm{cdiam}(P)>n-d. After Natura's O(m2log⁡m)O(m^2\log m) bound for standard-form polyhedra P={x:Ax=b,x≥0}P=\{x:Ax=b,x\ge 0\}, the question is exactly whether the linear Hirsch-type bound holds in the circuit setting, i.e. whether the quadratic-logarithmic gap can be closed to a linear bound (or whether the linear bound fails).

(2) The approximability status of diameter computation. For a polytope given in rational halfspace description, three sub-questions are each to be settled: (2a) whether the value of its monotone diameter mdiam\mathrm{mdiam} can be approximated within a constant factor in polynomial time; (2b) whether the value of its monotone circuit diameter mcdiam\mathrm{mcdiam} can be so approximated; and (2c) whether the ordinary circuit diameter cdiam(P)\mathrm{cdiam}(P) admits a constant-factor polynomial-time approximation at all, given that Wulf's inapproximability factor ε\varepsilon is of order 10−510^{-5} and does not rule out, say, a 2-approximation. Each of (2a)–(2c) is settled either by proving that the quantity in question is hard to approximate within some constant factor (the strengthening of the Nöbel–Steiner NP-hardness theorems that they remarked would be quite interesting but out of reach of their methods) or by a polynomial-time constant-factor approximation algorithm with a proven guarantee.

Both parts concern the same objects — the circuit and monotone diameters of polytopes — and share one objective: completing the quantitative (how large can these diameters be) and computational (how hard are they to compute or approximate) characterization that the NP-hardness results of 2018–2025 left open.

References

  1. Christian Nöbel, Raphael Steiner: Complexity of polytope diameters via perfect matchings. Mathematical Programming (2026), DOI 10.1007/s10107-026-02324-6; SODA 2025 version DOI 10.1137/1.9781611978322.74; arXiv:2404.04158 (v1 under the title 'Hardness of circuit and monotone diameters of polytopes'). https://arxiv.org/abs/2404.04158
  2. Lasse Wulf: Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings). FOCS 2025, DOI 10.1109/focs63196.2025.00029; arXiv:2502.16398. https://arxiv.org/abs/2502.16398
  3. Bento Natura: Circuit Diameter of Polyhedra is Strongly Polynomial. arXiv:2602.06958. https://arxiv.org/abs/2602.06958
  4. Daniel Dadush, Stefan Kober, Zhuan Khye Koh: On Circuit Diameter and Straight Line Complexity. arXiv:2602.05699. https://arxiv.org/abs/2602.05699
  5. Steffen Borgwardt, Elisabeth Finhold, Raymond Hemmecke: On the Circuit Diameter of Dual Transportation Polyhedra. SIAM Journal on Discrete Mathematics 29(1), 2015, DOI 10.1137/140976868; arXiv:1405.3184. https://arxiv.org/abs/1405.3184
  6. Laura Sanità: The Diameter of the Fractional Matching Polytope and Its Hardness Implications. FOCS 2018, DOI 10.1109/focs.2018.00090. https://doi.org/10.1109/focs.2018.00090
  7. Alan M. Frieze, Shang-Hua Teng: On the complexity of computing the diameter of a polytope. Computational Complexity 4, 1994, DOI 10.1007/bf01206636. https://doi.org/10.1007/bf01206636
  8. Francisco Santos: A counterexample to the Hirsch Conjecture. Annals of Mathematics 176(1), 2012, DOI 10.4007/annals.2012.176.1.7. https://doi.org/10.4007/annals.2012.176.1.7
  9. Jean Cardinal, Raphael Steiner: Inapproximability of shortest paths on perfect matching polytopes. Mathematical Programming, 2023, DOI 10.1007/s10107-023-02025-4; arXiv:2210.14608. https://arxiv.org/abs/2210.14608
  10. Steffen Borgwardt, Weston Grewe, Sean Kafer, Jon Lee, Laura Sanità: On the hardness of short and sign-compatible circuit walks. Discrete Applied Mathematics, 2025, DOI 10.1016/j.dam.2025.02.009; arXiv:2402.01066. https://arxiv.org/abs/2402.01066
  11. Alexander E. Black, Steffen Borgwardt, Matthias Brugger: On the circuit diameter conjecture for counterexamples to the Hirsch conjecture. Discrete Optimization, 2025, DOI 10.1016/j.disopt.2025.100910; arXiv:2302.03977. https://arxiv.org/abs/2302.03977
  12. Steffen Borgwardt, Tamon Stephen, Timothy Yusun: On the Circuit Diameter Conjecture. Discrete & Computational Geometry, 2018, DOI 10.1007/s00454-018-9995-y; arXiv:1611.08039. https://arxiv.org/abs/1611.08039
  13. Alexander E. Black, Christian Nöbel, Raphael Steiner: Short circuit walks in fixed dimension. arXiv:2510.01916. https://arxiv.org/abs/2510.01916
  14. Jesús A. De Loera, Sean Kafer, Laura Sanità: Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization. SIAM Journal on Optimization 32(3), 2022, DOI 10.1137/21m1419994; arXiv:1909.12863. https://arxiv.org/abs/1909.12863
  15. Sean Kafer, Kanstantsin Pashkovich, Laura Sanità: On the Circuit Diameter of Some Combinatorial Polytopes. SIAM Journal on Discrete Mathematics 33(1), 2019, DOI 10.1137/17m1152115; arXiv:1709.09642. https://arxiv.org/abs/1709.09642
  16. Daniel Dadush, Zhuan Khye Koh, Bento Natura, László A. Végh: On Circuit Diameter Bounds via Circuit Imbalances. arXiv:2111.07913. https://arxiv.org/abs/2111.07913