The combinatorial diameter of a dd-dimensional polyhedron with ff facets — the worst-case number of edge steps between two vertices — was conjectured by Hirsch to be at most f−df-d, but is now known to exceed this bound. The circuit diameter replaces edge steps by maximal steps along circuits, the minimal-support (potential edge) directions of the defining inequality system; since edges are circuits, it never exceeds the combinatorial diameter, so the bound f−df-d may still hold for it. The Circuit Diameter Conjecture (Borgwardt–Finhold–Hemmecke, 2015) asserts exactly this: ΔC(f,d)≤f−d\Delta_{\mathcal{C}}(f,d)\le f-d for every dd-dimensional polyhedron with ff facets, bounded or unbounded. Borgwardt, Stephen, and Yusun (2018) proved the conjecture equivalent to the circuit dd-step conjecture ΔC(2d,d)≤d\Delta_{\mathcal{C}}(2d,d)\le d, settled the first nontrivial case ΔC(8,4)=4\Delta_{\mathcal{C}}(8,4)=4 (in particular, the Klee–Walkup unbounded Hirsch counterexample satisfies the circuit bound), and later work (Black–Borgwardt–Brugger, 2023/2025) showed the remaining known Hirsch counterexamples do not transfer to circuit walks either. The conjecture remains open in both directions: the linear bound ΔC(f,d)≤f−d\Delta_{\mathcal{C}}(f,d)\le f-d is neither proved nor refuted, while the first open case of the dd-step chain is d=5d=5.

Background

For a convex polyhedron PP of dimension dd with ff facets, the combinatorial (graph) diameter is the largest number of edges needed to walk between any two vertices along the edge graph of PP. Because the simplex method for linear programming moves along edges, this diameter lower-bounds the best-case number of simplex pivots; Hirsch conjectured in the late 1950s that it is at most f−df-d. Klee and Walkup (1967) disproved the bound for unbounded polyhedra with a 4-dimensional, 8-facet polyhedron U4U_4 of diameter 5, and proved the general conjecture equivalent to several seemingly weaker statements: the dd-step conjecture (the bound for polyhedra with exactly 2d2d facets), the non-revisiting conjecture (any two vertices are joined by a walk that never re-enters a facet it has left), and the Dantzig-figure conjecture (the bound for the distance between the two special vertices of a Dantzig figure, a polyhedron with 2d2d facets of which dd are incident to one of the two distinguished vertices and dd to the other). Their equivalence machine relies on the wedge construction, which stacks a polytope into one higher dimension to control facet incidences. For bounded polytopes the Hirsch bound survived until Santos's counterexample (2012), later reduced to dimension 20 by prismatoid constructions of Matschke, Santos, and Weibel.

Circuit diameter relaxes edge walks. For P={z:Az≥b}P=\{z:Az\ge b\} given by an irredundant inequality system, the circuits of PP are the normalized directions gg for which AgAg has minimal support — the elementary vectors of the row system; geometrically they are all potential edge directions, that is, the edge directions of every polyhedron obtained from PP by translating facets. A circuit walk moves from a boundary point of PP by a maximal step along a circuit direction, landing where the boundary blocks further movement, then continues with another circuit; unlike an edge walk it may cross the relative interior of faces and pass through non-vertex boundary points, and it is not reversible (reversing a maximal circuit walk need not give a circuit walk). The circuit diameter of PP is the maximum, over pairs of vertices, of the length of a shortest circuit walk between them, and ΔC(f,d)\Delta_{\mathcal{C}}(f,d) denotes the worst case over all dd-dimensional polyhedra with ff facets. Since edges are circuits, the circuit diameter never exceeds the combinatorial diameter, so the Hirsch bound can fail for edge walks while still holding for circuit walks. A related 'feasible' walk notion allows non-maximal steps; the Circuit Diameter Conjecture concerns the maximal-step version above. A crucial difference from the combinatorial setting is realization dependence: two polyhedra with the same combinatorial type can have different circuit diameters, which Borgwardt, Stephen, and Yusun handle by proving it suffices to study C\mathcal{C}-simple polyhedra (those in which shortest circuit walks between vertices always enter exactly one new facet per step, in the sense that each step drops the previously blocking facet and is blocked by a single new one).

Borgwardt, Finhold, and Hemmecke introduced the circuit diameter in 2015, in a study of dual transportation polyhedra, and conjectured the circuit analogue of the Hirsch bound: the Circuit Diameter Conjecture, ΔC(f,d)≤f−d\Delta_{\mathcal{C}}(f,d)\le f-d for all f≥df\ge d. Borgwardt, Stephen, and Yusun (2018) then built the circuit analogue of the Klee–Walkup program. Their Theorem 1.1 shows that the circuit non-revisiting conjecture (and its equivalent f=2df=2d and 'any start' variants) implies the Circuit Diameter Conjecture, and that the Circuit Diameter Conjecture is equivalent to the circuit dd-step conjecture ΔC(2d,d)≤d\Delta_{\mathcal{C}}(2d,d)\le d for all dd. Their Theorem 1.2 shows that non-revisiting circuit walks in bounded polytopes up to dimension dd would imply the linear bound ΔC(f,d)≤f−1\Delta_{\mathcal{C}}(f,d)\le f-1 for all unbounded polyhedra — a bounded-to-unbounded connection with no combinatorial counterpart. They prove the circuit 44-step conjecture ΔC(8,4)=4\Delta_{\mathcal{C}}(8,4)=4 twice: once through the uniqueness of the Klee–Walkup type U4U_4 among simple non-Hirsch (8,4)(8,4)-polyhedra (the bounded obstruction being the 9-facet, diameter-5 polytope Q4Q_4, which becomes U4U_4 when a facet is projected to infinity), and once through non-revisiting facial paths in 4-dimensional prismatoids (a prismatoid is a polytope whose vertices all lie on two distinguished facet bases; its polar is a spindle, a polytope with two apex vertices such that every facet contains exactly one apex — these objects produced the Hirsch counterexamples), strengthening a result of Santos, Stephen, and Thomas on the width of 4-dimensional prismatoids. The paper also records that no clear path to the general circuit dd-step conjecture is presently visible, while it views the circuit 55-step conjecture as approachable by adapting either of the methods that settled the 44-step case: an enumerative analysis of the simple (10,5)(10,5)-polyhedra (a polyhedron is simple if every vertex lies on exactly dd of its facets), extending the uniqueness argument for U4U_4, or a proof that 55-dimensional spindles with 99 facets on one side and 55 on the other satisfy the non-revisiting conjecture.

What breaks the classical program is that the wedge construction fails for circuit walks: a circuit walk in a wedge over PP need not project to a circuit walk in PP. Consequently, the implication from the Circuit Diameter Conjecture back to the non-revisiting conjecture is open; the known reduction of the general problem to the (2d,d)(2d,d) case passes through an unbounded intermediate polyhedron, so it cannot be used for the bounded versions of the conjectures; and the position of the circuit Dantzig-figure conjecture in the implication hierarchy is unresolved. The source paper also records open existence questions about Hirsch-sharp realizations (realizations whose circuit diameter equals f−df-d): whether every non-regular realization of the dd-cube meets the bound, whether the Klee–Walkup polyhedron U4U_4 has a 'collapsing' realization of circuit diameter below 4, and whether Q4Q_4 has any Hirsch-sharp realization at all.

Problem Statement

Prove or refute the Circuit Diameter Conjecture: for every polyhedron PP of dimension dd with ff facets, bounded or unbounded, is the circuit diameter of PP at most f−df-d; equivalently, is ΔC(f,d)≤f−d\Delta_{\mathcal{C}}(f,d)\le f-d for all f≥df\ge d? By Theorem 1.1 of Borgwardt, Stephen, and Yusun, this is equivalent to the circuit dd-step conjecture: ΔC(2d,d)≤d\Delta_{\mathcal{C}}(2d,d)\le d for every dd. The first open case of this chain is the circuit 55-step conjecture — is the circuit diameter of every 55-dimensional polyhedron with 1010 facets at most 55? Settling the circuit 55-step case alone is partial progress toward the conjecture, not a resolution of it.

References

  1. Steffen Borgwardt, Tamon Stephen, Timothy Yusun. 'On the Circuit Diameter Conjecture.' Discrete & Computational Geometry 60 (2018) 558–587. DOI: 10.1007/s00454-018-9995-y; arXiv:1611.08039. https://arxiv.org/abs/1611.08039
  2. Steffen Borgwardt, Elisabeth Finhold, Raymond Hemmecke. 'On the Circuit Diameter of Dual Transportation Polyhedra.' SIAM Journal on Discrete Mathematics 29 (2015) 113–121. DOI: 10.1137/140976868. https://doi.org/10.1137/140976868
  3. Tamon Stephen, Timothy Yusun. 'The Circuit Diameter of the Klee-Walkup Polyhedron.' Electronic Notes in Discrete Mathematics 49 (2015) 505–512. DOI: 10.1016/j.endm.2015.06.070. https://doi.org/10.1016/j.endm.2015.06.070
  4. Alexander E. Black, Steffen Borgwardt, Matthias Brugger. 'On the Circuit Diameter Conjecture for Counterexamples to the Hirsch Conjecture.' Discrete Optimization 58 (2025) 100910. DOI: 10.1016/j.disopt.2025.100910; arXiv:2302.03977. https://arxiv.org/abs/2302.03977
  5. Sean Kafer, Kanstantsin Pashkovich, Laura Sanità. 'On the Circuit Diameter of Some Combinatorial Polytopes.' SIAM Journal on Discrete Mathematics 33 (2019) 1–25. DOI: 10.1137/17m1152115; arXiv:1709.09642. https://arxiv.org/abs/1709.09642
  6. Daniel Dadush, Zhuan Khye Koh, Bento Natura, László A. Végh. 'On Circuit Diameter Bounds via Circuit Imbalances.' Mathematical Programming 206 (2024) 631–662. DOI: 10.1007/s10107-024-02107-x; arXiv:2111.07913. https://arxiv.org/abs/2111.07913
  7. Bento Natura. 'Circuit Diameter of Polyhedra is Strongly Polynomial.' arXiv:2602.06958 (2026). https://arxiv.org/abs/2602.06958
  8. Daniel Dadush, Stefan Kober, Zhuan Khye Koh. 'On Circuit Diameter and Straight Line Complexity.' arXiv:2602.05699 (2026). https://arxiv.org/abs/2602.05699
  9. Alexander E. Black, Christian Nöbel, Raphael Steiner. 'Short Circuit Walks in Fixed Dimension.' Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2026) 563–573. DOI: 10.1137/1.9781611978971.23; arXiv:2510.01916. https://arxiv.org/abs/2510.01916
  10. Victor Klee, David W. Walkup. 'The d-step conjecture for polyhedra of dimension d < 6.' Acta Mathematica 117 (1967) 53–78. DOI: 10.1007/BF02395040. https://doi.org/10.1007/BF02395040
  11. Francisco Santos. 'A Counterexample to the Hirsch Conjecture.' Annals of Mathematics 176 (2012) 383–412. DOI: 10.4007/annals.2012.176.1.7. https://doi.org/10.4007/annals.2012.176.1.7
  12. Francisco Santos, Tamon Stephen, Hugh Thomas. 'Embedding a Pair of Graphs in a Surface, and the Width of 4-dimensional Prismatoids.' Discrete & Computational Geometry 47 (2012) 569–576. DOI: 10.1007/s00454-011-9361-9. https://doi.org/10.1007/s00454-011-9361-9
  13. Benjamin Matschke, Francisco Santos, Christophe Weibel. 'The width of five-dimensional prismatoids.' Proceedings of the London Mathematical Society 110 (2015) 647–672. DOI: 10.1112/plms/pdu064. https://doi.org/10.1112/plms/pdu064
  14. Jesús A. De Loera, Sean Kafer, Laura Sanità. 'Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization.' SIAM Journal on Optimization 32 (2022) 2156–2179. DOI: 10.1137/21m1419994; arXiv:1909.12863. https://arxiv.org/abs/1909.12863
  15. Alexander E. Black, Lei Xue. 'Any Proof of Polynomial Hirsch Must be Completely Incoherent.' arXiv:2607.11628 (2026). https://arxiv.org/abs/2607.11628