Integer programs with nearly totally unimodular matrices: the cographic case
<|reference_start|>Integer programs with nearly totally unimodular matrices: the cographic case: It is a notorious open question whether integer programs (IPs), with an integer coefficient matrix $M$ whose subdeterminants are all bounded by a constant $\Delta$ in absolute value, can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from $M$, one obtains a submatrix $A$ that is the transpose of a network matrix.   Our approach focuses on the case where $A$ arises from $M$ after removing $k$ rows only, where $k$ is a constant. We achieve our result in two main steps, the first related to the theory of IPs and the second related to graph minor theory.   First, we derive a strong proximity result for the case where $A$ is a general totally unimodular matrix: Given an optimal solution of the linear programming relaxation, an optimal solution to the IP can be obtained by finding a constant number of augmentations by circuits of $[A\; I]$.   Second, for the case where $A$ is transpose of a network matrix, we reformulate the problem as a maximum constrained integer potential problem on a graph $G$. We observe that if $G$ is $2$-connected, then it has no rooted $K_{2,t}$-minor for $t = \Omega(k \Delta)$. We leverage this to obtain a tree-decomposition of $G$ into highly structured graphs for which we can solve the problem locally. This allows us to solve the global problem via dynamic programming.<|reference_end|>
@article{aprile2024integer,
    title={Integer programs with nearly totally unimodular matrices: the cographic
  case},
    author={Manuel Aprile and Samuel Fiorini and Gwena"el Joret and Stefan Kober
  and Micha{l} T. Seweryn and Stefan Weltge and Yelena Yuditsky},
    journal={arXiv preprint arXiv:2407.09477},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.09477},
    primaryClass={math.CO cs.DM cs.DS math.OC}
}