Totally $Δ$-Modular Tree Decompositions of Graphic Matrices for Integer Programming
For researchers in integer programming and combinatorial optimization, this provides a new tractable class of integer programs, though the extension is incremental over existing treewidth-based methods.
The paper introduces a new parameter, totally Δ-modular treewidth (TDM-treewidth), for matrices with two nonzero entries per row, and shows that integer programs with bounded TDM-treewidth and bounded variable domains can be solved in polynomial time. This extends previous graph-based decomposition parameters to matrices with entries outside {-1,0,1}.
We introduce the tree-decomposition-based parameter totally $Δ$-modular treewidth (TDM-treewidth) for matrices with two nonzero entries per row. We show how to solve integer programs whose matrices have bounded TDM-treewidth in polynomial time when variables have bounded domain. This extends previous graph-based decomposition parameters for matrices with at most two nonzero entries per row to include matrices with entries outside of $\{-1,0,1\}$. We also give an analogue of the Grid Theorem of Robertson and Seymour for matrices of bounded TDM-treewidth in the language of rooted signed graphs.