The bounded-entry tree-structured integer-programming conjecture

Fix a positive integer dd. Let AA be a matrix with exactly two nonzero entries per row, let G(A)G(A) be its associated graph, and suppose that G(A)G(A) is a tree and ∥A∥∞≤d\|A\|_\infty\leq d. For integer vectors w,bw,b and bounds ℓ,u\ell,u, consider the integer program

max⁡{wTx:Ax≤b, x∈[ℓ,u]∩Zn}.\max\{w^Tx: Ax \leq b,\ x \in [\ell,u]\cap\mathbb{Z}^n\}.

Bounded-entry tree integer-programming conjecture. The integer program can be solved in polynomial time for constant dd.

This is presented as a simpler unresolved case of polynomial-time solvability for bounded-entry matrices with tree structure. The supplied text does not give a resolution status beyond stating that it is not known.

References

Primary source

Caleb McFarland, “Totally Δ-Modular Tree Decompositions of Graphic Matrices for Integer Programming”, arXiv:2602.01499 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.