Integer programs with nearly totally unimodular matrices: the cographic case
Manuel Aprile, Samuel Fiorini, Gwenaël Joret, Stefan Kober, Miehał T. Seweryn, Stefan Weltge, Yelena Yuditsky · Society for Industrial and Applied Mathematics eBooks · 2025
It is a notorious open question whether integer programs (IPs) with an integer coefficient matrix M whose subdeterminants are all bounded by a constant Δ 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.