The bounded-entry tree-structured integer-programming conjecture

From papers

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 Ad\|A\|_\infty\leq d. For integer vectors w,bw,b and bounds ,u\ell,u, consider the integer program

max{wTx:Axb, 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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.