Bounded circuit-lcm subspaces: conformal circuit decompositions of lattice vectors and recognition beyond total unimodularity

The lcm-circuit imbalance measure $\dot{\kappa}_W$ of a rational subspace $W\subseteq\mathbb{R}^n$ — the least common multiple, over all elementary vectors (support-minimal vectors) of $W$, of the entry magnitudes of their primitive integer representatives — is the smallest $k$ making every polyhedron $\{x\in W+d:x\ge 0\}$ with $d\in\mathbb{Z}^n$ $1/k$-integral, and is the arithmetic counterpart of the circuit imbalance measures that parameterize current linear programming algorithms. The structural open problems posed by Ekbatani–Natura–Végh (Surveys in Combinatorics 2022) on this measure are: (Q1) their Conjecture 10.1.1, that every integer vector $z\in W\cap\mathbb{Z}^n$ admits a conformal decomposition into at most $n$ elementary vectors of $W$, each $1/\dot{\kappa}_W$-integral — equivalently, that every Graver basis element of an integer matrix is such a conformal sum; and (Q2) whether the classes $\dot{\kappa}_A\le k$ for fixed $k$, starting with $k=2$ (half-integral polyhedra), admit polynomial-time recognition and a Seymour-type decomposition theory extending the totally unimodular case. No resolution of either question is known in the literature to date, and both components remain open; the partial results established so far are stated in the Background.

Background

Linear programming and integer programming theory is increasingly parameterized by properties of the constraint matrix alone; this problem concerns the arithmetic side of that program. For a linear subspace $W\subseteq\mathbb{R}^n$, a nonzero vector $g\in W$ is an elementary vector if its support (the set of indices where it is nonzero) is inclusion-minimal among the supports of nonzero vectors of $W$; these supports are the circuits of $W$. The elementary vectors with a common support form a one-dimensional subspace, so if $W$ is rational (it admits a rational basis), each has, up to sign, a unique primitive representative $g^C$ with integer entries of greatest common divisor 1. Two vectors are conformal if they never point in opposite sign directions coordinate-wise ($u_i v_i\ge 0$ for all $i$).

Ekbatani, Natura, and Végh's survey (Surveys in Combinatorics 2022) systematizes three measures of how unbalanced the elementary vectors of $W$ can be: the fractional circuit imbalance $\kappa_W=\max|g^C_j/g^C_i|$ over all circuits $C$ and coordinates $i,j\in C$; the max-circuit imbalance $\bar{\kappa}_W=\max_C\|g^C\|_\infty$; and the lcm-circuit imbalance $\dot{\kappa}_W=\mathrm{lcm}\{\mathrm{lcm}(g^C): C \text{ a circuit}\}$, where $\mathrm{lcm}(v)$ is the least common multiple of the absolute values of the entries of $v$. For a matrix $A$, the same notation abbreviates the corresponding quantity of the null space: $\dot{\kappa}_A=\dot{\kappa}_{\ker(A)}$, and analogously for $\kappa$ and $\bar{\kappa}$. A vector is $1/k$-integral if every entry is an integer multiple of $1/k$. The fractional measure governs continuous properties (error bounds for linear systems, interior-point iteration counts, and diameters of polyhedra, i.e., lengths of shortest edge-paths between vertices), whereas $\dot{\kappa}_W$ governs integrality: it is the smallest $k$ such that for every integer translate $d\in\mathbb{Z}^n$ the polyhedron $\{x\in W+d: x\ge 0\}$ is $1/k$-integral, that is, every vertex has all entries in $\frac{1}{k}\mathbb{Z}$ — a far-reaching generalization of the classical characterization of totally unimodular matrices through integrality of polyhedra.

The case $\dot{\kappa}_W=1$ is classical. A matrix is totally unimodular (TU) if every square subdeterminant is $0$ or $\pm 1$; a subspace is the kernel of a TU matrix exactly when its lcm-circuit imbalance equals $1$ (a regular subspace), and Seymour's 1980 decomposition theorem — every regular matroid is assembled from graphic, cographic, and one sporadic block by $1$-, $2$-, and $3$-sums — yields a polynomial-time algorithm deciding whether a matrix is TU. The next class, $\dot{\kappa}\in\{1,2\}$ (half-integral polyhedra), already contains important families: integer matrices $A$ whose every column satisfies $\sum_i|A_{ij}|\le 2$ (at most two nonzero entries, each of absolute value at most $2$), and the binet matrices obtained from such matrices by basis inversion. Whether this class — and more generally the class $\dot{\kappa}_A\le k$ for fixed $k$ — admits an analogous structural characterization and polynomial-time recognition is open, already for $k=2$; the survey poses this as the question of extending Seymour's decomposition beyond total unimodularity.

For integer programming, the central object is the Graver basis $\mathcal{G}(A)$ of an integer matrix $A$: the conformally indecomposable elements of $\ker(A)\cap\mathbb{Z}^n$, that is, those lattice vectors in the kernel that cannot be split into a sum of two nonzero conformal lattice vectors of the kernel. Graver bases drive augmentation algorithms and proximity bounds for integer programs, and their norms are sandwiched around circuit imbalance ($\bar{\kappa}_A\le\max_{g\in\mathcal{G}(A)}\|g\|_\infty\le n\bar{\kappa}_A$). Every vector $z\in W$ admits a conformal decomposition into at most $n$ elementary vectors of $W$, but only with real coefficients; nothing in general is known about the denominators of the summands. The survey's Conjecture 10.1.1 asserts an arithmetic refinement: the denominators are controlled by $\dot{\kappa}_W$ alone. This is known to hold when $\dot{\kappa}_W=1$; when $W$ can be rescaled by positive coordinate scalings to the case $\dot{\kappa}=1$ (by a theorem of Lee this includes every $\dot{\kappa}_W=p^\alpha$ with $p$ an odd prime); and for $\dot{\kappa}_W=2^\alpha$ whenever $z$ admits a conformal circuit decomposition with at most three summands.

The motivation is the quest for linear programming algorithms whose running time depends only on the constraint matrix: current frameworks solve LP with only polylogarithmic dependence on the circuit imbalance of $A$, so structural knowledge of bounded-imbalance classes is a main lever towards a strongly polynomial LP algorithm — one using a number of arithmetic operations polynomial in the dimensions but independent of the input encoding length, listed by Smale among the mathematical problems for the twenty-first century and still open.

Problem Statement

The problem is to settle the structural theory of rational subspaces with bounded lcm-circuit imbalance — the extension, beyond total unimodularity, of the decomposition and recognition theory that Seymour's theorem provides for the case $\dot{\kappa}=1$. Two linked questions constitute the common objective.

(Q1) The conformal circuit decomposition conjecture (Conjecture 10.1.1 of Ekbatani–Natura–Végh). Let $W\subseteq\mathbb{R}^n$ be a rational linear subspace. Is it true that for every $z\in W\cap\mathbb{Z}^n$ there exists a conformal circuit decomposition

$z=\sum_{k=1}^{h} g^k,\qquad h\le n,$

such that each summand $g^k$ is an elementary vector of $W$ and is $1/\dot{\kappa}_W$-integral? Equivalently, as the survey notes, it suffices to answer it for Graver basis elements: is every element of the Graver basis of an integer matrix $A$ with $\ker(A)=W$ a conformal sum of at most $n$ elementary vectors of $W$ whose entries are multiples of $1/\dot{\kappa}_W$? A proof settles the conjecture affirmatively; a refutation is an explicit rational subspace $W$ and vector $z\in W\cap\mathbb{Z}^n$ (for instance a Graver basis element) that admits no such decomposition, together with a rigorous nonexistence argument.

(Q2) Recognition and decomposition of the bounded circuit-lcm classes. For fixed $k$ — minimally for $k=2$ — decide whether a given rational matrix $A$ satisfies $\dot{\kappa}_A\le k$ in polynomial time, and determine whether the class admits a Seymour-type structural decomposition theorem composed from natural building blocks (for $k=2$, integer matrices $A$ whose every column satisfies $\sum_i|A_{ij}|\le 2$ — at most two nonzero entries, each of absolute value at most $2$ — and matrices obtained from them by basis inversion are the natural candidates).

The overarching question of a strongly polynomial algorithm for linear programming, and the complexity of computing exact values of $\dot{\kappa}_A$ when it is not bounded by a fixed constant, motivate this problem but are not part of its completion boundary.

References

1. 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 481, Cambridge University Press, pp. 64–114, 2022. DOI: 10.1017/9781009093927.004; arXiv:2108.03616. https://arxiv.org/abs/2108.03616
2. P. D. Seymour: Decomposition of regular matroids. Journal of Combinatorial Theory, Series B 28(3):305–359, 1980. DOI: 10.1016/0095-8956(80)90075-1. https://doi.org/10.1016/0095-8956(80)90075-1
3. Jon Lee: Subspaces with well-scaled frames. Linear Algebra and its Applications 114–115:21–56, 1989. DOI: 10.1016/0024-3795(89)90450-3. https://doi.org/10.1016/0024-3795(89)90450-3
4. Jon Lee: The incidence structure of subspaces with well-scaled frames. Journal of Combinatorial Theory, Series B 50(2):265–287, 1990. DOI: 10.1016/0095-8956(90)90082-B. https://doi.org/10.1016/0095-8956(90)90082-B
5. Gautam Appa, Balázs Kotnyek: Rational and integral k-regular matrices. Discrete Mathematics 275(1–3):1–15, 2004. DOI: 10.1016/S0012-365X(03)00095-5. https://doi.org/10.1016/S0012-365X(03)00095-5
6. Konstantinos Papalamprou, Leonidas Pitsoulis, Balász Kotnyek: A mathematical programming approach for recognizing binet matrices. Optimization Letters 18(6):1511–1532, 2024. DOI: 10.1007/s11590-023-02066-w. https://doi.org/10.1007/s11590-023-02066-w
7. Daniel Dadush, Sophie Huiberts, Bento Natura, László A. Végh: A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix. Mathematical Programming 204(1–2):135–206, 2023. DOI: 10.1007/s10107-023-01956-2; arXiv:1912.06252. https://arxiv.org/abs/1912.06252
8. Richard Cole, Christoph Hertrich, Yixin Tao, László A. Végh: A first order method for linear programming parameterized by circuit imbalance. Mathematical Programming 216(1–2):339–377, 2025. DOI: 10.1007/s10107-025-02264-7; arXiv:2311.01959. https://arxiv.org/abs/2311.01959
9. Daniel Dadush, Friedrich Eisenbrand, Rom Pinchasi, Thomas Rothvoss, Neta Singer: Excluding a line minor via design matrices and column number bounds for the circuit imbalance measure. Preprint, 2025. arXiv:2510.20301. https://arxiv.org/abs/2510.20301
10. Marcin Brianski, Martin Koutecký, Daniel Král, Kristýna Pekárková, Felix Schröder: Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming. Preprint, 2022. arXiv:2202.05299. https://arxiv.org/abs/2202.05299
11. Steffen Borgwardt, Weston Grewe, Sean Kafer, Jon Lee, Laura Sanità: On the hardness of short and sign-compatible circuit walks. Discrete Applied Mathematics 367:129–149, 2025. DOI: 10.1016/j.dam.2025.02.009; arXiv:2402.01066. https://arxiv.org/abs/2402.01066
12. Shmuel Onn: Circuit and Graver walks and linear and integer programming. Discrete Optimization 54:100862, 2024. DOI: 10.1016/j.disopt.2024.100862; arXiv:2410.00656. https://arxiv.org/abs/2410.00656
13. Bento Natura: Circuit Diameter of Polyhedra is Strongly Polynomial. Preprint, 2026. arXiv:2602.06958. https://arxiv.org/abs/2602.06958
14. Jakub Komárek, Martin Koutecký: Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization. In 22nd International Symposium on Experimental Algorithms (SEA 2024), Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 18:1–18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. DOI: 10.4230/LIPIcs.SEA.2024.18. https://doi.org/10.4230/LIPIcs.SEA.2024.18
15. Levent Tunçel: Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard. Mathematical Programming 86(1):219–223, 1999. DOI: 10.1007/s101070050087. https://doi.org/10.1007/s101070050087
16. Steffen Borgwardt, Nicholas Crawford, Sean Kafer, Jon Lee, Angela Morrison: On Circuit Imbalance and 0/1 Circuits for Coloring and Spanning Forest Problems. Preprint, 2025. arXiv:2512.05223. https://arxiv.org/abs/2512.05223
17. 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