Strongly polynomial circuit augmentation toward an unknown optimal vertex of a linear program

Natura (2026) proved that the circuit diameter of a polyhedron $P=\{x\in\mathbb{R}^{n}:Ax=b,x\geq 0\}$ with $A\in\mathbb{R}^{m\times n}$ is $O(m^{2}\log m)$ — the first strongly polynomial bound, settling the polynomial version of the circuit diameter conjecture — and showed that such walks can be taken monotone with respect to the objective and constructed in strongly polynomial time between any two given vertices. The construction, however, requires knowing the target vertex, and computing an optimal vertex is precisely the linear programming problem itself. The open problem posed by the source — in its abstract and in the Section 1.2 discussion 'Existence versus Computation' — is whether one can design a circuit-augmentation rule that, starting from an arbitrary feasible solution and without knowing the target vertex in advance, always reaches an optimal vertex in strongly polynomially many circuit augmentation steps. A positive answer would yield a strongly polynomial-time algorithm for linear programming, resolving Smale's 9th problem. The question is open (Natura, 2026); adjacent 2026 results only sharpen the hardness of computing shortest monotone walks and rule out coherent path families.

Background

Linear programming — minimizing a linear objective over a polyhedron — is solved in practice by the simplex method, which walks along vertices and edges of the feasible region. Its worst-case pivot count is governed by the combinatorial diameter of the polyhedron: the maximum, over pairs of vertices, of the length of a shortest path in the vertex–edge graph. The Hirsch conjecture (1957) asserted that a $d$-dimensional polytope with $f$ facets has combinatorial diameter at most $f-d$; it was disproved by Santos (2012), but the polynomial Hirsch conjecture — whether the diameter is always bounded by a polynomial in $f$ and $d$ — remains open, with only quasipolynomial bounds known.

For a polyhedron in standard equality form $P=\{x\in\mathbb{R}^{n}:Ax=b,x\geq 0\}$ with $A\in\mathbb{R}^{m\times n}$ of row rank $m$, the elementary vectors (also called circuits) of the constraint matrix are the support-minimal nonzero vectors of $\ker(A)$: nonzero vectors $g$ such that no nonzero $h\in\ker(A)$ has $\mathrm{supp}(h)\subsetneq\mathrm{supp}(g)$. Every edge direction of $P$ is an elementary vector, and as the right-hand side $b$ varies, the elementary vectors exhaust all possible edge directions, so walks along elementary vectors relax edge walks. A circuit walk is a sequence of feasible points in which each step moves from $x$ to $x+\alpha g$ for an elementary vector $g$ and a maximal step size $\alpha>0$ (the largest value with $x+\alpha g\in P$). The circuit diameter of $P$ is the worst-case length of a shortest circuit walk between two vertices; it lower-bounds the iteration count of any circuit augmentation algorithm, an algorithm that, like the simplex method, moves from feasible point to feasible point along circuit steps. A circuit walk is monotone with respect to an objective $c$ if $c^{\top}x$ never increases along it; monotone walks are what augmentation algorithms for LP actually traverse. The step requirement is asymmetric (circuit walks need not be reversible), which is a recurring technical obstacle.

Borgwardt, Finhold, and Hemmecke (2015) introduced the circuit diameter, proved linear bounds for dual transportation polyhedra, and posed the circuit analogue of the Hirsch conjecture; the polynomial circuit diameter conjecture asks only for a $\mathrm{poly}(m,n)$ bound. All prior general upper bounds were merely weakly polynomial: they depended either on the bit size of the input or on the circuit imbalance measure $\kappa(A)$, the maximum ratio between nonzero entries of an elementary vector (equal to $1$ exactly for totally unimodular matrices, those whose every square subdeterminant is $0$ or $\pm1$). Ekbatani, Natura, and Végh (2022) obtained $O(n^{2}m\kappa(A)\log(\kappa(A)+n))$ via minimum-mean-cycle-style arguments, and Dadush, Koh, Natura, and Végh (2024) improved this to $O(m^{2}\log(\kappa(A)+m))$ using a 'shoot towards the optimum' scheme that takes an optimal vertex as input. Here 'weakly polynomial' versus 'strongly polynomial' refers to whether the bound depends on the encoding length of the input numbers or only on the dimensions $(m,n)$ — the distinction at the heart of Smale's 9th problem (Smale, 1998), which asks for a strongly polynomial-time algorithm for linear programming. All known general LP algorithms (ellipsoid, interior point) are only weakly polynomial; strongly polynomial algorithms are known only for restricted matrix classes, such as Tardos's framework for bounded-subdeterminant integer matrices (1986) and the algorithm of Dadush, Koh, Natura, Olver, and Végh (2024) for matrices with at most two nonzeros per row or column, and log-barrier path-following interior point methods were proven not strongly polynomial by Allamigeon, Benchimol, Gaubert, and Joswig (2018).

Natura (2026) proved the first strongly polynomial bound: the circuit diameter of $P$ is $O(m^{2}\log m)$, the bound holds for the monotone circuit diameter as well, and a circuit walk of length $n+O(m^{2}\log m)$ from any feasible point to any given target vertex can be constructed in strongly polynomial time, settling the polynomial circuit diameter conjecture. The construction uses the target vertex essentially: it decomposes $x^{*}-x$ conformally (a conformal circuit decomposition writes a kernel vector as a sum of elementary vectors whose sign patterns agree with it), maintains 'trapped' coordinates within a factor $m$ of their target values, and forces combinatorial progress with extrapolation steps whose thresholds are polynomially small independent of condition numbers. Onn (2024) similarly showed that a circuit walk from a feasible point to an optimal point is polynomial-time computable given the solution of the LP. Everything known is therefore about walking to a known or already-computed target.

Meanwhile the surrounding complexity landscape hardened. De Loera, Kafer, and Sanità (2022) proved that finding a $2$-approximation of the shortest monotone circuit walk is NP-hard given the LP and the starting vertex. Black, Nöbel, and Steiner (2026) strengthened this to NP-hardness of approximating the shortest monotone circuit walk within a factor $O(m^{1-\varepsilon})$ for any $\varepsilon>0$, even for polygons in fixed dimension, which is essentially best possible for that case. Black and Steiner (2026) showed that even computing a shortest monotone edge path to the optimum over a simple polytope (a polytope in which every vertex lies on exactly $d$ facets, where $d$ is the dimension) — equivalently, a shortest sequence of simplex pivots — is NP-hard, already for fractional knapsack polytopes. Black and Xue (2026) proved that coherent monotone paths — monotone vertex paths induced by regular subdivisions in the fiber-polytope sense, such as shadow-vertex-type paths realizable as projections of monotone paths of a higher-dimensional polytope — can be exponentially long, refuting the coherent analogue of the polynomial Hirsch conjecture. Consequently, a rule that navigates to an unknown optimum cannot aim for (near-)shortest walks and cannot come from the natural globally coherent path families; it must find some short walk by other means.

Problem Statement

Let $A\in\mathbb{R}^{m\times n}$ have row rank $m$, let $b\in\mathbb{R}^{m}$ and $c\in\mathbb{R}^{n}$, and consider the linear program $\min\{c^{\top}x:x\in P\}$ over $P=\{x\in\mathbb{R}^{n}:Ax=b,x\geq 0\}$; throughout, the LP is assumed to attain its optimum, that is, $P$ is assumed to contain a $c$-optimal vertex. Recall that a circuit augmentation step moves from a feasible point $x$ to $\mathrm{aug}_{P}(x,g)=x+\alpha g$, where $g$ is an elementary vector of $\ker(A)$ (a nonzero vector in $\ker(A)$ with inclusion-minimal support: no nonzero $h\in\ker(A)$ satisfies $\mathrm{supp}(h)\subsetneq\mathrm{supp}(g)$) and $\alpha>0$ is maximal with $x+\alpha g\in P$.

The problem, posed as the leading open question of Natura (2026): does there exist a circuit-augmentation algorithm — one that is given only $(A,b,c)$ and a feasible starting point (or computes one in strongly polynomial time), performs circuit augmentation steps, and in particular is not given any optimal vertex and does not first solve the LP or an auxiliary LP to optimality — such that for every such instance it terminates at a $c$-optimal vertex after at most $O(m^{2}\log m)$ augmentation steps, or indeed after any number of steps bounded by a strongly polynomial function of the dimensions $(m,n)$ (for example the $n+O(m^{2}\log m)$ form of the source's Theorem 3.1), with the direction and maximal step length of each augmentation computable in strongly polynomial time?

Equivalently: the existence of short (indeed monotone) circuit walks toward every vertex is now known, and such a walk can be constructed in strongly polynomial time when the target vertex is given; can such a walk be found when the target optimum is not known in advance? A positive answer yields a strongly polynomial-time algorithm for linear programming, resolving Smale's 9th problem. A complete negative answer requires formalizing the class of permitted target-free rules (an explicit information or query model for step selection) and proving that every rule in that class requires super-polynomially many augmentations on some family of instances.

The source remarks (Section 1.2) that the focus now shifts toward understanding what structure might enable efficient navigation without knowing the target. A further companion question in the source — closing the $O(m^{1+\varepsilon}\log m)$ gap between the constructive $O(m^{2}\log m)$ upper bound and the $m^{1-\varepsilon}$ inapproximability of shortest monotone circuit walks — is recorded as adjacent context rather than as part of this problem's completion boundary.

References

1. Bento Natura. Circuit Diameter of Polyhedra is Strongly Polynomial. arXiv:2602.06958 (2026), DOI 10.48550/arxiv.2602.06958. https://arxiv.org/abs/2602.06958
2. Alexander E. Black, Christian Nöbel, Raphael Steiner. Short circuit walks in fixed dimension. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 563-573, SIAM, 2026. DOI 10.1137/1.9781611978971.23; preprint arXiv:2510.01916 (2025). https://doi.org/10.1137/1.9781611978971.23
3. Daniel Dadush, Stefan Kober, Zhuan Khye Koh. On Circuit Diameter and Straight Line Complexity. arXiv:2602.05699 (2026). https://arxiv.org/abs/2602.05699
4. Alexander E. Black, Raphael Steiner. Finding Short Paths on Simple Polytopes. arXiv:2603.05482 (2026). https://arxiv.org/abs/2603.05482
5. Alexander E. Black, Lei Xue. Any Proof of Polynomial Hirsch Must be Completely Incoherent. arXiv:2607.11628 (2026). https://arxiv.org/abs/2607.11628
6. Daniel Dadush, Zhuan Khye Koh, Bento Natura, László A. Végh. On circuit diameter bounds via circuit imbalances. Mathematical Programming 206(1-2):631-662 (2024), DOI 10.1007/s10107-024-02107-x. https://doi.org/10.1007/s10107-024-02107-x
7. Steffen Borgwardt, Elisabeth Finhold, Raymond Hemmecke. On the Circuit Diameter of Dual Transportation Polyhedra. SIAM Journal on Discrete Mathematics 29(1):113-121 (2015), DOI 10.1137/140976868. https://doi.org/10.1137/140976868
8. Jesús A. De Loera, Sean Kafer, Laura Sanità. Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization. SIAM Journal on Optimization 32(3):2156-2179 (2022), DOI 10.1137/21M1419994. https://doi.org/10.1137/21M1419994
9. Shmuel Onn. Circuit and Graver walks and linear and integer programming. Discrete Optimization 54:100862 (2024), DOI 10.1016/j.disopt.2024.100862. https://doi.org/10.1016/j.disopt.2024.100862
10. Steve Smale. Mathematical problems for the next century. The Mathematical Intelligencer 20(2):7-15 (1998), DOI 10.1007/BF03025291. https://doi.org/10.1007/BF03025291
11. Francisco Santos. A Counterexample to the Hirsch Conjecture. Annals of Mathematics 176(1):383-412 (2012), DOI 10.4007/annals.2012.176.1.7. https://doi.org/10.4007/annals.2012.176.1.7
12. Éva Tardos. A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs. Operations Research 34(2):250-256 (1986), DOI 10.1287/opre.34.2.250. https://doi.org/10.1287/opre.34.2.250
13. Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig. Log-Barrier Interior Point Methods Are Not Strongly Polynomial. SIAM Journal on Applied Algebra and Geometry 2(1):140-178 (2018), DOI 10.1137/17m1142132. https://doi.org/10.1137/17m1142132
14. Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver, László A. Végh. A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or Column. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), pp. 1561-1572, DOI 10.1145/3618260.3649764. https://doi.org/10.1145/3618260.3649764
15. Farbod Ekbatani, Bento Natura, László A. Végh. Circuit Imbalance Measures and Linear Programming. In Surveys in Combinatorics 2022, London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 64-114 (2022), DOI 10.1017/9781009093927.004; preprint arXiv:2108.03616 (2021). https://doi.org/10.1017/9781009093927.004