Polynomial-time bounded sub-determinant integer programs

Conjecture on polynomial-time solvability of bounded sub-determinant integer programs · arXiv:1908.06300

arXiv Informal medium confidence— first stated 2019-08-17

Authors: Michele Conforti, Samuel Fiorin, Tony Huynh, Gwenaël Joret, Stefan Weltge

Status partial high confidence

The conjecture has two components: the general claim that all bounded sub-determinant integer programs are polynomial-time solvable, and the specific claim that the stable set problem is polynomial for every fixed odd cycle packing bound $k$. The latter was settled by arXiv:2106.05947 (FOCS 2021), which gives the first polynomial-time algorithm for the weighted stable set problem on graphs with at most $k$ vertex-disjoint odd cycles for any constant $k$, extending the previously known cases $k=0$ (bipartite) and $k=1$. The broader claim about all bounded sub-determinant IPs remains open in full generality; known positive results cover bimodular matrices and matrices with at most two nonzero entries per row.

Cited literature (1)

partial Integer programs with bounded subdeterminants and two nonzeros per row (2021)

authors unverified; see arXiv:2106.05947 · Proceedings of the 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 13-24 · arXiv:2106.05947

Proves the first polynomial-time algorithm for the weighted stable set problem on graphs with at most k vertex-disjoint odd cycles (any constant k), thereby resolving the graph-theoretic 'in particular' part of the conjecture; the general bounded sub-determinant IP claim is addressed only for coefficient matrices with at most two nonzero entries per row.

Reviewer notes. The 'in particular' part of the conjecture (stable set polynomial for every fixed ocp bound k) is proved by arXiv:2106.05947 (FOCS 2021). The broader conjecture that all bounded sub-determinant IPs are polynomial remains open; partial progress includes bimodular matrices (Artmann-Weismantel-Zenklusen, STOC 2017) and matrices with two nonzeros per row (arXiv:2106.05947). Authors of 2106.05947 could not be confirmed from fetched abstract content; the URL was verified via two WebFetch calls.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. Integer programs with bounded sub-determinants can be solved in polynomial time. In particular, the stable set problem on graphs with $\mathrm{ocp}(G) \leq k$ is polynomial for every fixed $k$.

Context

The authors note that recent work links the complexity of integer programs to the magnitude of their sub-determinants, and that it is tempting to believe bounded sub-determinant integer programs are polynomial-time solvable. This would imply the stable set problem is polynomial for every fixed bound $k$ on the odd cycle packing number, which remains open for $k \geq 2$.

Notes. Stated as 'it is tempting to believe'; the paper explicitly confirms the problem is open for $k \geq 2$. No labelled theorem environment.

Source paper

The stable set problem in graphs with bounded genus and bounded odd cycle packing number
Michele Conforti, Samuel Fiorin, Tony Huynh, Gwenaël Joret, Stefan Weltge · 2019-08-17
https://arxiv.org/abs/1908.06300 PDF source