zbMATH — the first resource for mathematics

Integer programming and incidence treedepth. (English) Zbl 1436.90083
Lodi, Andrea (ed.) et al., Integer programming and combinatorial optimization. 20th international conference, IPCO 2019, Ann Arbor, MI, USA, May 22–24, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11480, 194-204 (2019).
Summary: Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matrix on the other side. To that end, integer linear programming is fixed-parameter tractable with respect to the primal (or dual) treedepth of the Gaifman graph of its constraint matrix and the largest coefficient (in absolute value). Motivated by this, M. Koutecký, A. Levi and S. Onn [“A parameterized strongly polynomial algorithm for block structured integer programs”, LIPIcs – Leibniz Int. Proc. Inform. 107, Article 85, 14 p. (2018; doi:10.4230/LIPIcs.ICALP.2018.85)] asked whether it is possible to extend these result to a more broader class of integer linear programs. More formally, is integer linear programming fixed-parameter tractable with respect to the incidence treedepth of its constraint matrix and the largest coefficient (in absolute value)?
We answer this question in negative. We prove that deciding the feasibility of a system in the standard form, \({A\mathbf{x}= \mathbf{b}}\), \({\mathbf{l}\le\mathbf{x}\le\mathbf{u}}\), is NP-hard even when the absolute value of any coefficient in \(A\) is 1 and the incidence treedepth of \(A\) is 5. Consequently, it is not possible to decide feasibility in polynomial time even if both the assumed parameters are constant, unless \(\mathrm{P}=\mathrm{NP}\).
For the entire collection see [Zbl 1418.90011].
90C10 Integer programming
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI