Hard problems on box-totally dual integral polyhedra

Chervet, Patrick;Grappe, Roland;Lacroix, Mathieu;Pisanu, Francesco;Wolfler Calvo, Roberto

2023-01-01

---

Abstract

In this paper, we study the complexity of some fundamental questions regarding box-totally dual integral (box-TDI) polyhedra. First, although box-TDI polyhedra have strong integrality properties, we prove that Integer Programming over box-TDI polyhedra is NP-complete, that is, finding an integer point optimizing a linear function over a box-TDI polyhedron is hard. Second, we complement the result of Ding et al. specialIntscript who proved that deciding whether a given system is box-TDI is co-NP-complete: we prove that recognizing whether a polyhedron is box-TDI is co-NP-complete.To derive these complexity results, we exhibit new classes of totally equimodular matrices - a generalization of totally unimodular matrices - by characterizing the total equimodularity of incidence matrices of graphs.