A rational linear system is totally dual integral (TDI) if for every inte-
ger linear function for which the optimum is finite the associated dual
problem has an integer optimal solution. A TDI system is box-TDI
if adding any rational bounds on the variables preserves its TDIness.
Box-TDI systems are systems that yield strong min-max relations such
as the one involved in the Max Flow-Min Cut Theorem of Ford and
Fulkerson. A polyhedron is box-TDI if it can be described by a box-
TDI system.
Box-total dual integral systems and polyhedra received a lot of atten-
tion from the combinatorial optimization community around the 80's.
A renewed interest appeared in the last decade and since then many
deep results appeared involving such systems.
In this talk, we study the complexity of some fundamental questions re-
garding 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
maximizing a linear function over a box-TDI polyhedron is hard. Sec-
ond, we complement the result of Ding, Tan, and Zang 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.